对于最优化的子数组问题，一名话，就是从给你的数组中寻找一个子数组，使得它的和是最优的（最大/最小）
假如求最大子数组：
如果数组中元素全是正的，那么好办，整个数组的和就是了。
如果数组中元素全是负的，那么也好办，找最小的那个。
但是如果正负相间呢？？？
如上图中，如何求出那个最大的子数组呢？
显然我们可以穷举，但是好像不现实。
于昰我们采用将原问题划分成许多子问题也就是分治策略：
如果我们能设计这样一函数
这个函数的作用是在数组A中，从low 到 high中求出最大子数组。
但是对于最大子数组问题，子数组的出现，可能在以下三个情况中：
于是我们还另外设计一种特殊情况：、
也就是跨越中点的情况，于是我们采用将原问题不停地折半的思路将原问题划原许多子问题。
整 体思路：
对于跨越中点的子数组：
有个地方值得注意：
上述中，我们的sum是一直在加的，就是防止有这种情况-1 ，-1，-1，10，···········
虽然前面有三个-1 ，但是后面有个10，肯定都得加上。
原代码：
#include<iostream>#define MIN -255; struct returnVal{ int left; int right; int sum;}; struct returnVal*findMaxCrossingSubarray(int left,int mid ,int right,int *arr); struct returnVal *findMaxSubarray(int left,int right ,int *arr); struct returnVal*findMaxCrossingSubarray(int left,int mid ,int right,int *arr){ int leftMaxSum=MIN; int sum=0; int maxLeft=0; int i,j; for(i=mid ; i>=left; i--){ sum+=arr[i]; if(sum>leftMaxSum){ leftMaxSum=sum; maxLeft=i; } } sum=0; int rightMaxSum=MIN; int maxRight=0; for(int j=mid+1; j<=right; j++){ sum+=arr[j]; if(sum>rightMaxSum){ rightMaxSum=sum; maxRight=j; } } struct returnVal *val=new returnVal; val->left=maxLeft; val->right=maxRight; val->sum=rightMaxSum+leftMaxSum; return val;}inline struct returnVal* maxThree_returnVal(struct returnVal *left,struct returnVal *mid,struct returnVal *right){ if(left->sum>=mid->sum&&left->sum>=right->sum){ return left; } if(right->right>=left->sum&&right->sum>=mid->sum){ return right; } if(mid->sum>=left->sum&&mid->sum>=right->sum){ return mid; }}struct returnVal *findMaxSubarray(int left,int right ,int *arr){ if(left==right){ struct returnVal *val=new returnVal; val->left=left; val->right=right; val->sum=arr[left]; return val; } struct returnVal *valRight; struct returnVal *valCross; struct returnVal *valLeft; int mid=(left+right)/2; valLeft=findMaxSubarray(left,mid,arr); valRight=findMaxSubarray(mid+1,right,arr); valCross=findMaxCrossingSubarray(left,mid,right,arr); return maxThree_returnVal(valLeft,valCross,valRight); }
测试代码：
int arr[16]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7}; int main(){ struct returnVal *val=new returnVal; val=findMaxSubarray(0,15,arr); std::cout<<val->left<<","<<val->right<<","<<val->sum<<std::endl; }
结果：
来自为知笔记(Wiz)
转载于:https://www.cnblogs.com/yml435/p/4655522.html
