- #include<stdio.h>
- struct T{
- int i,j;
- int maxSub;
- };
- struct T maxSubString(int s[], int low, int high){
- struct T t;
- if(high - low == 0){
- t.i = low;
- t.j = high;
- t.maxSub = s[low];
- return t;
- }
- else{
- struct T t1,t2,t3;
- int mid = (high + low)/2;
- t1 = maxSubString(s, low, mid);
- t2 = maxSubString(s, mid+1, high);
- t3.maxSub = s[mid] + s[mid+1];
- for(int i=mid; i>=low; i--){
- for(int j=mid; j<=high; j++){
- int sum = 0;
- for(int k=i; k<=j; k++){
- sum += s[k];
- }
- if(t3.maxSub < sum){
- t3.i = i;
- t3.j = j;
- t3.maxSub = sum;
- }
- }
- }
- if(t1.maxSub > t2.maxSub){
- if(t1.maxSub > t3.maxSub)
- return t1;
- else
- return t3;
- }
- else{
- if(t2.maxSub > t3.maxSub)
- return t2;
- else
- return t3;
- }
- }
- }
- int main(){
- int s[] = {-2, 11, -4, 13, -5, -2};
- struct T t;
- t = maxSubString(s, 0, 5);
- printf("%d,%d,%d", t.i, t.j, t.maxSub );
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/0705201512515.html
来源: http://www.codesnippet.cn/detail/0705201512515.html