algorithm - 我该如何解决这个动态规划问题？

Question

我在学习动态规划时遇到了一个问题。

我有一串数字。你需要找到这个字符串中前半部分数字和后半部分数字之和的子串中最长的子串的长度。

例如，

输入字符串:142124

输出:6

当输入字符串为“142124”时，前半部分的数字(142)和后半部分的数字(124)之和相同，因此整个给定的字符串成为我们找到的最长子串。因此，输出为6，即整个字符串的长度。

输入字符串:9430723

输出:4

此字符串中前半部分和后半部分之和的最长子串成为“4307”。

我是这样解决这个问题的

int maxSubStringLength(char* str){ 
int n = strlen(str);
int maxLen = 0;

int sum[n][n];

for(int i=0; i<n; i++)
    sum[i][i] = str[i] - '0';

for(int len =2; len <=n; len++){
    for(int i = 0; i < n - len + 1; i++){
        int j = i + len - 1;
        int k = len / 2;
        sum[i][j] = sum[i][j-k] + sum[j-k+1][j];

        if(len%2 == 0 && sum[i][j-k] == sum[j-k+1][j] && len > maxLen)
            maxLen = len;
        }
    }
    return maxLen;
}

这段代码的时间复杂度为O(n * n)，空间复杂度为O(n * n)。

但是，这个问题需要O (1) 空间复杂度和O (n * n) 时间复杂度来解决。

是否可以用O(1)的空间复杂度来解决这个问题？

Answer 1

你可以很容易地用 O(1) 的空间复杂度和 O(n^2) 的时间复杂度来解决这个问题。

这是一种方法:

1. 从 m = 0 到 n-2。这表示字符串的中间(您在第 m 个字符之后拆分)。

2. 对于 i = 1 到 n(如果超出范围则中断)。构建左右总和，如果它们相等，则将 i 与目前最好的进行比较，如果更好则更新它。

3. 解是2倍最佳(因为它表示半串)。

在 Java 中它会是这样的:

public int maxSubstringLength(String s) {
    int best = 0;
    for (int m = 0; m < s.length() - 1; m++) {
        int l = 0; // left sum
        int r = 0; // right sum
        for (int i = 1; m - i + 1 >= 0 && m + i < s.length(); i++) {
            l += s.charAt(m - i + 1);
            r += s.charAt(m + i);
            if (l == r && i > best)
                best = i;
        }
    }
    return 2 * best;
}