问题：给定由n个整数（包含负整数）组成的序列a1,a2,…,an，求该序列子段和的最大值。 当所有整数均为负值时定义其最大子段和为0。 所求的最优值为： 分析： 从问题的解的结构可以看出，它适合于用分治策略求解： 如果将所给的序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种情形： a[1:n]的最大子段和与a[1:n/2]的最大子段和相同； a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同； a[1:n]的最大子段和为下面的形式。
#include<iostream> using namespace std; #define NUM 1001 int a[NUM]; int MaxSum(int n){ int sum=0; //最大子段和 int b=0; //1~j的最大子段和，因无需保留其他结果，所以没必要定义数组 for (int i=1;i<=n;i++) { if (b>0) b+=a[i]; else b=a[i]; if (b>sum) sum=b; } return sum; } int main(){ }