Как я могу решить эту проблему программирования Dynami c? - PullRequest
Новая
       91

Как я могу решить эту проблему программирования Dynami c?

3 голосов
/ 26 января 2020

Я застрял в проблеме изучения динамического c программирования.

У меня есть строка чисел. Вам нужно найти длину самой длинной подстроки подстрок в этой строке, которая имеет сумму первой половины чисел и второй половины чисел.

Например,

Входная строка : 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)?

1 Ответ

3 голосов
/ 26 января 2020

Вы можете легко решить эту проблему с O (1) пространственной сложностью и O (n ^ 2) временной сложностью.

Вот один подход:

  1. Go от 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;
}
...