最大子数组和问题：
给定一个数组A[0,1...,N-1]，求A的连续子数组，使得该子数组和最大。
如：数组：1，-2，3，10，-4，7，2，-5
子数组：3，10，-4，7，2；该子数组和为 18。
程序实现：
1 /*************************************** 2 FileName MaxSumSubArray.cpp 3 Author : godfrey 4 CreatedTime : 2016/5/4 5 ****************************************/ 6 #include <iostream> 7 #include <cstring> 8 #include <vector> 9 #include <algorithm> 10 #include <stdio.h> 11 #include <stdlib.h> 12 13 using namespace std; 14 15 int MaxSumSubArray(int* A,int size,int& from,int& to){ 16 if( !A || size <= 0){//错误检测 17 from = -1; 18 to = -1; 19 return 0; 20 } 21 from = to = 0; 22 int sum = A[0];//当前子串的和 23 int result = sum;//当前子串的最优解 24 int FromUpdate; 25 for(int i=1;i<size;i++){ 26 if(sum > 0){ 27 sum += A[i]; 28 } 29 else{ 30 sum = A[i]; 31 FromUpdate = i;//在sum<0时，更新子数组起点 32 } 33 34 if(result < sum){//当前最优解更新的时候，起点终点都更新 35 result = sum; 36 from = FromUpdate; 37 to = i; 38 } 39 } 40 return result; 41 } 42 int main() 43 { 44 int a[] = {1,-2,3,10,-4,7,2,-5}; 45 int start,end; 46 int result = MaxSumSubArray(a,sizeof(a)/sizeof(int),start,end); 47 cout<<"the MaxSumSubArray: "; 48 cout<<result<<endl; 49 cout<<"start: "<<start<<" end: "<<end<<endl; 50 cout<<"The subArray is : "<<endl; 51 for(int i = start;i<=end;i++){ 52 cout<<a[i]<<" "; 53 } 54 cout<<endl; 55 return 0; 56 }
运行结果：
转载请注明出处：
C++博客园：godfrey_88