ThinkChat2.0新版上线,更智能更精彩,支持会话、画图、阅读、搜索等,送10W Token,即刻开启你的AI之旅 广告
###问题 > 给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0,依此定义,所求的最优值为: Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如,当(a[1],a[2],a[3],a[4],a[5],a[6])=(-2,11,-4,13,-5,-2)时,最大子段和为20。 ###思路 从第一个元素开始,计算1-2的和、1-3的和、直到1-n的和,sum来记录最大的和,在循环过程中如果有和比sum大,把当前最大和替换掉,记录besti和bestj;然后计算2-3的和、2-4的和、直到2-n的和。需要2次for循环,时间复杂度O(n^2). ###代码 ~~~ #include <iostream> using namespace std; //求a中的最大子段和 int maxSum(int a[],int n){ int i,j,sum=0,besti,bestj; for(i=0;i<4;i++){ int newsum=0; for ( j= i; j <n; ++j) { newsum+=a[j]; if(newsum>sum){ sum=newsum; besti=i; bestj=j; } } } cout<<"开始位置:"<<a[besti]<<endl; cout<<"开始位置:"<<a[bestj]<<endl; return 0; } int main(){ int a[6]={-2,11,-4,13,-5,-2}; maxSum(a,6); int b[10]={1,-5,6,-2,11,-7,23,-13,15,-3}; maxSum(b,10); } ~~~ ###输出 ~~~ 开始位置:11 开始位置:13 开始位置:6 开始位置:15 ~~~ ###时间复杂度 O(n^2)