一、最大子段和
问题
给定N个数A1, A2, ... An，从中选出k（k不固定）个连续的数字 Ai, Ai+1, ... Ai+k-1，使得∑i+k−1iAt 达到最大，求该最大值。
分析 求最大子段和可以用多种算法来解决. （1）直接枚举
max = 0;for i in [1...n] for j in [i....n] sum = 0; for k in [i...j] sum += A[k] if(sum > max) max = sum//时间复杂度为O(n^3)
（2）求 sum[i...j]时，直接利用 sum[i...j] = sum[i...j-1] + A[j]来优化
max = 0;for i in [1...n] sum = 0 for j in [i....n] sum += A[j] if(sum > max) max = sum//时间复杂度为O(n^2)
（3）分治法 将A1...An用二分法分为左右两边，则A1...An中的最大连续子段和可能为三种情况： 【1】是A1...An/2中的最大连续子段和 【2】是An/2+1....An中的最大连续子段和 【3】横跨 左右两边
int MaxSum(int* a, int beg, int end){ if (beg == end){ return a[beg] > 0? a[beg] :0; } int mid = (beg + end) / 2; int max_left = MaxSum(a, beg, mid); int max_right = MaxSum(a, mid + 1 ,end); int s1 = 0, s2 = 0, m_left = 0, m_right = 0; for(int i = mid; i <= beg; i --){ s1 += a[i]; if(s1 > m_left) m_left = s1; } for(int i = mid+1; i <= end; i ++){ s2 += a[i]; if(s2 > m_right) m_right = s2; } int max_sum = max_left; if(max_right > max_sum) max_sum = max_right; if(m_right + m_left > max_sum) max_sum = m_left + m_right; return max_sum;}//时间复杂度为 O(nlogn)
（4）动态规划算法 用动归数组 dp[i]表示以Ai结尾的若干个连续子段的和的最大值，则有递推公式： dp[i] = max{dp[i-1] + A[i], A[i]}
int max = 0;for(int i = 1; i <= n; i ++){ if(dp[i-1] > 0){ dp[i] = dp[i-1] + A[i]; }else{ dp[i] = A[i]; } if(dp[i]> max){ max = dp[i]; }}//时间复杂度为O(n)
二、最大子矩阵和
问题
给定MxN的矩阵，其子矩阵R{x1, y1, x2, y2} (x1, y1) 为矩阵左上角的坐标，(x2, y2)为矩阵右下角的坐标，S(x1,y1,x2,y2)表示子矩阵R中的数字的和，求所有子矩阵的和的最大值。
分析 矩阵有M行，line1, line2....lineM. 先限制行为从第i行到第j行，任意两列k和l，形成的一个子矩阵中元素的和： 由于行已经限定为第i行到第j行，则形成的子矩阵的和可以视为将第i行到第j行按照行相加得到一个一维数组T，选择T中k个元素到第l个元素之间的元素和。这又归为一个求最大子段和问题。 即先选定行范围（比如从第i行到第j行），求所选定行元素按列相加得到一维数组，再求该一维数组的最大子段和
int sum_line[M][M];for(int i =1; i <= n; i ++){ sum_line[1][i] = A[1][i];}for(int i = 2; i <= m; i ++){ for(int k = 1;k <= n; k ++){ sum_line[i][k] = sum_line[i-1][k] + A[i][k]; }}for(int i = 1; i <= m; i ++){ for(int j = i; j <= m; j ++){ int b = 0; for(int k = 1; k <= n; k ++){ if(b > 0){ b += (sum_line[j][k] - sum_line[i-1][k]); }else{ b = sum_line[j][k] - sum_line[i-1][k]; } if(b > max){ max = b; } } }}//时间复杂度为 O(m*m*n)
三、最大M子段和
问题
给定N个数，从中选出M个不重叠的连续子段，使得这些连续子段的和值最大，求该最大的和值。
分析 f[i][j]表示将A[1...j]这些数分成i个不相交的连续子段，且A[j]为第i个子段的末尾，这i个子段和的最大值。则有动归方程 f[i][j] = max{f[i][j-1] + A[j], max{f[i-1][k]} k = i-1, i+1...j - 1} 第一种情况是将A[1...j-1]分为i个不相交的连续子段，A[j-1]在第i个子段的末尾；此时再加上A[j]使得且A[j]和A[j-1]均位于第i个子段； 第二种情况是将A[1...k]分为i-1个不同的子段，A[k]位于第i-1个子段的末尾；此时加上A[j]使得A[j]单独成为第i个子段
辅助数组进行优化 f[i][j]表示将A[1...i]这些数分成j个不相交的连续子段(注意这里是将前i个数分成j个不相交的子段），且A[i]为第j个子段的末尾，这j个子段和的最大值；g[i][j]表示将A[1...i]这些数分成j个不相交的连续子段，且A[i]不一定为第j个子段的末尾，这j个子段和的最大值。 则有递推关系： f[i][j] = max{f[i-1][j] + A[i], g[i-1][j-1] + A[i]} //对应两种情况：1. A[i]至少和前面的一个数位于第j个子段内；2. A[i] 自己位于第j个子段内
g[i][j] = max{g[i-1][j], f[i][j]} //对应两种情况：1. A[i]不在第j个子段内，这相当于将 A[1...i-1]划分为j个子段 2. A[i]位于第j个子段内
long long int f[MAX_LEN];long long int g[MAX_LEN];int A[MAX_LEN];/*f[i][j] 表示将A[1...i] 划分为j个不相交连续子串，且A[j]属于第i个子串，所能达到的最大子串和g[i][j] 表示将A[1...j] 划分为i个不相交连续子串，且A[j]不一定属于第i个子串，所能达到的最大子串和f[i][j] = max{f[i-1][j] + A[i], g[i-1][j-1] + A[i]}g[i][j] = max{g[i-1][j], f[i][j]};进行空间优化之后：f[j] = max{f[j], g[j-1]} + A[i]g[j - 1] = max(g[j - 1], f[j - 1]);注意f和g的循环层次不同这是因为：在外部进行到第i层循环的时候，f[i][j] = max{f[i-1][j] + A[i], g[i-1][j-1] + A[i]} 中max{}中的 f[j]和g[j-1]用的是第i-1层循环的时候的 f[j]和 g[j-1]； 若写成f[j] = max(f[j] + A[i], g[j - 1] + A[i]);g[j] = max(g[j], f[j]);则本次的g[j]变成了第i次循环的g[j]，而下次循环的 f[j] = max{} 中 g[j-1]变成了第i次循环的g[j]，而不是第i-1次循环的g[j]因此，写成 g[j-1] = max(g[j-1], f[j-1]); 使得 每次执行for (j = 1; j <= m; j++){ f[j] = max(f[j] + A[i], g[j-1] + A[i]); g[j-1] = max(g[j-1], f[j-1]);}的时候， f[j]都使用第i-1层的f[j]和g[j-1]，而g[j-1]使用的是第i-1层的g[j-1]和第i层的f[j]*/long long int MaxSum(int m, int n){ int i, j; for (i = 1; i <= n; i++){ for (j = 1; j <= m; j++){ f[j] = max(f[j] + A[i], g[j-1] + A[i]); g[j-1] = max(g[j-1], f[j-1]); } g[j - 1] = max(g[j - 1], f[j - 1]); } return g[m];}