动态规划之最大子段和问题

问题描述：

给定长度为n的整数序列，a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大.或者求出最大的这个和.例如(-2,11,-4,13,-5,2)的最大子段和为20,所求子区间为[2,4].

1.穷举法

枚举左右区间然后遍历该区间求解，时间复杂度O(n³)

2.穷举法+前缀和

在第一种方法的基础上，预处理出前缀和，在枚举左右区间之后，可以通过前缀和直接求解，例如求[l, r]区间的和，直接用sum[r] - sum[l - 1]求出。时间复杂度O(n²)（前缀和sum[i]表示前i位之和）

3.分治法

求解时分治，[1, n]的最大子段和只可能出现在[1, n / 2]或者[n / 2 = 1, n]或者起点位于[1, n / 2]，后者位于[n / 2 + 1, n]。就可以直接分治最大子段和。时间复杂度O(nlog(n))。

 1 int maxsum(int *a, int x, int y)//返回左闭右开区间的最大连续和
 2 {
 3     if(y - x == 1)return a[x];//只有一个元素，直接返回
 4     int m = (x + y) / 2;
 5     int maxs = max(maxsum(a, x, m), maxsum(a, m, y));//递归求解左右区间的最大值
 6     int v = 0, L = a[m - 1], R = a[m];
 7     //L为从分界点往左的最大连续和， R为分界点往右的最大连续和
 8     for(int i = m - 1; i >= x; i--)L = max(L, v += a[i]);
 9     v = 0;//清空之前的v
10     for(int i = m; i < y; i++)R = max(R, v += a[i]);
11     return max(maxs, L + R);//合并求解
12 }

4.动态规划法

设dp[i]为以i结尾的最大子段和，那对于dp[i]而言只有两种情况，如果dp[i - 1] > 0, 那么dp[i] = dp[i - 1] + a[i];不然，dp[i] = a[i]，然后求出dp数组中的最大值即可。

 1 ll dp[maxn], a[maxn];
 2 int main()
 3 {
 4     cin >> n;
 5     for(int i = 1; i <= n; i++)
 6     {
 7         cin >> a[i];
 8         dp[i] = a[i];
 9     }
10     for(int i = 1; i <= n; i++)
11     {
12         dp[i] = max(dp[i], dp[i - 1] + a[i]);
13     }
14     ll ans = 0;
15     for(int i = 1; i <= n; i++)ans = max(ans, dp[i]);
16     cout<<ans<<endl;
17     return 0;
18 }

其实，可以进行空间上的优化，根本不需要dp数组，也不需要a数组，只需要两个变量即可，一个保存我当前的和，一个保存最大和，如果当前和>最大和，更新最大和，如果当前和<0,则设置当前和 = 0；

 1 　　cin >> n;
 2     ll maxsum = 0;
 3     ll thissum = 0;
 4     int x;
 5     for(int i = 1; i <= n; i++)
 6     {
 7         cin >> x;
 8         thissum += x;
 9         if(thissum > maxsum)
10         {
11             maxsum = thissum;
12         }
13         if(thissum < 0)
14         {
15             thissum = 0;
16         }
17     }
18     cout<<maxsum<<endl;

最大子段和变形：记录开始和结束点