就是每个从i开始到数组结尾的最大和，等于前m个元素单独划分，再加上剩下元素的最大和。这k中划分方案最大的，就是从i开始到数组结尾最大和最大的。
依次计算到第0个位置结束。
为了计算统一，会用到sum(n),实际没有这个元素，初始化零计算即可。
代码：
class Solution { public: int dp[501]={0}; int maxSumAfterPartitioning(vector<int>& A, int K) { int n = A.size(); for(int i = n-1; i>=0; --i) { int ma = 0; int j; for(j=i;j<i+K && j < n ;++j) { ma = max(ma, A[j]); dp[i] = max(dp[i], ma*(j - i + 1) + dp[j + 1]); } } return dp[0]; } }; 最长重复子串题目：
最长重复子串(Longest Duplicate Substring)
地址：
https://leetcode-cn.com/contest/weekly-contest-136/problems/longest-duplicate-substring/
题意：
给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。
返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 ""。）
思路：
后缀数组教科书般的例题。
后缀数组是后缀树的一种变种，能够节省空间。构造的方法有「倍增算法」，「DC3算法」。
主要思想：
设字符串为S(1-n)由n个字符组成。则字符串有n个相同后缀的子串。分别为s(1-n),s(2-n),...,s(n-n)。
然后构建一个SA数组，每个数组存储这些后缀的子串，存储后进行字典序排序。
最后构造出一个height数组，表示SA数组每个元素和前一个元素相同前缀的字符个数。
那么，最长重复子串的长度就是height数组的最大值。
因为最长重复子串一定是两个不同后缀的公共前缀，而且这两个不同后缀的字典序排列后一定是相连的。否则一定有比他更长的。
所以height的最大值能够找到那两个后缀，然后提取公共前缀就找到答案。
代码：
namespace SA { bool cmp(int *r, int a, int b, int l) { return r[a] == r[b] && r[a + l] == r[b + l]; } void da(int str[], int sa[], int rank[], int height[], int n, int m) { n++; int i, j, p, *x = t1, *y = t2; for (i = 0; i < m; i++) c[i] = 0; for (i = 0; i < n; i++) c[x[i] = str[i]]++; for (i = 1; i < m; i++) c[i] += c[i - 1]; for (i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i; for (j = 1; j <= n; j <<= 1) { p = 0; for (i = n - j; i < n; i++) y[p++] = i; for (i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j; for (i = 0; i < m; i++) c[i] = 0; for (i = 0; i < n; i++) c[x[y[i]]]++; for (i = 1; i < m; i++) c[i] += c[i - 1]; for (i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i]; swap(x, y); p = 1; x[sa[0]] = 0; for (i = 1; i < n; i++) x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++; if (p >= n) break; m = p; } int k = 0; n--; for (i = 0; i <= n; i++) rank[sa[i]] = i; for (i = 0; i < n; i++) { if (k) k--; j = sa[rank[i] - 1]; while (str[i + k] == str[j + k]) k++; height[rank[i]] = k; } } int num_rank[MAXN], height[MAXN]; int num[MAXN]; int sa[MAXN]; } // namespace SA class Solution { public: string longestDupSubstring(string S) { using namespace SA; int pos = 0; int len = 0; int n = S.length(); for (int i = 0; i <= n; ++i) { num[i] = S[i]&0x3f; } num[n] = 0; da(num, sa, num_rank, height, n, 256); for (int i = 2; i <= n; ++i) { if (height[i] > len) { pos = sa[i]; len = height[i]; } } return S.substr(pos, len); } };