题解 | #子数组的最大累加和问题#

这里使用二维dp数组保存最大连续子数组的长度，找到最大长度和 最大长度的连续字串的最后一个字符，也即是index = ans <= dp[i][j] ? i : index; ans = max(dp[i][j], ans);这两句代码分别寻找当前的最大长度和当前连续数组的末尾字符下标

class Solution {
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string getstring(string str1, int index, int len) {
        string s = "";
        for (int i = index-len; i < index; i++)
            s += str1[i];
        return s;
    }

    string LCS(string str1, string str2) {
        int m = str1.size();
        int n = str2.size();
        int ans = 0;
        int index = 0;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1[i - 1] == str2[j - 1])  dp[i][j] = dp[i - 1][j - 1] + 1;
                index = ans <= dp[i][j] ? i : index;
                ans = max(dp[i][j], ans);

            }
        }
        return getstring(str1, index, ans);
    }
};