求最大子数组之和的分治算法

#include <stdio.h>#include <limits.h>typedef struct _node{ int left; int right; int sum;}Node;void findCrossSubArr(int *arr,int low,int mid,int high,Node *crossResult){ int left_sum=INT_MIN; int sum=0; int i=mid; for(;i>=low;i–) { sum=sum+arr[i]; if(sum>left_sum) { left_sum=sum; crossResult->left=i; } } int right_sum=INT_MIN; sum=0; i=mid+1; for(;i<=high;i++) { sum=sum+arr[i]; if(sum>right_sum) { right_sum=sum; crossResult->right=i; } } crossResult->sum=left_sum+right_sum; }void findMaxSubArr(int *arr,int low,int high,Node *result){ if(low==high) { result->left=low; result->right=low; result->sum=arr[low]; return; } int mid=(low+high)>>1; Node leftResult; Node rightResult; findMaxSubArr(arr,low,mid,&leftResult); findMaxSubArr(arr,mid+1,high,&rightResult); Node crossResult; findCrossSubArr(arr,low,mid,high,&crossResult); if((leftResult.sum)>=(rightResult.sum)&&(leftResult.sum)>=(crossResult.sum)) { result->left=leftResult.left; result->right=leftResult.right; result->sum=leftResult.sum; return ; } else if((rightResult.sum)>=(leftResult.sum)&&(rightResult.sum)>=(crossResult.sum)) { result->left=rightResult.left; result->right=rightResult.right; result->sum=rightResult.sum; return ; } else { result->left=crossResult.left; result->right=crossResult.right; result->sum=crossResult.sum; return ; } }int main(){ Node result; int arr[]={1,-2,3,10,-4,7,2,-5}; int len=sizeof(arr)/sizeof(arr[0]); findMaxSubArr(arr,0,len-1,&result); printf(“%d\n”,result.left); printf(“%d\n”,result.right); printf(“%d\n”,result.sum); system(“pause”); return 0;}

，孤独是为了孤独背后的解脱，孤独的过程，就是一个寻找真爱的过程。