Найти максимальную сумму смежных вспомогательных массивов - еще одна версия

Question

В этом форуме есть много сообщений для нахождения наибольшего суммарного субарама. Тем не менее, небольшая вариация этой проблемы заключается в том, что подэлемент должен иметь по крайней мере два элемента.

Например, для ввода [-2, 3, 4, -5, 9, -13, 100, -101, 7] приведенный ниже код дает 100. Но с указанным ограничением это будет 98 с подмножеством [3, 4, -5, 9 , -13, 100]. Может ли кто-нибудь помочь мне сделать это? Я не мог получить правильную логику для этого.

#include<stdio.h> 
int maxSubArraySum(int a[], int size) 
{ 
    int max_so_far = 0, max_ending_here = 0; 
    int i; 
    for(i = 0; i < size; i++) 
    { 
    max_ending_here = max_ending_here + a[i]; 
    if(max_ending_here < 0) 
     max_ending_here = 0; 
    if(max_so_far < max_ending_here) 
     max_so_far = max_ending_here; 
    } 
    return max_so_far; 
} 

/*Driver program to test maxSubArraySum*/ 
int main() 
{ 
    int a[] = {-2, 3, 4, -5, 9, -13, 100, -101, 7}; 
    int n = sizeof(a)/sizeof(a[0]); 
    int max_sum = maxSubArraySum(a, n); 
    printf("Maximum contiguous sum is %d\n", max_sum); 
    getchar(); 
    return 0; 
} 

Update 1: Сделано изменение в соответствии с starrify, но я не понимаю, что я ожидал. Это дает 183 вместо 98.

#include<stdio.h> 

const int size = 9; 

int maxSubArraySum(int a[]) 
{ 
    int max_so_far = 0; 
    int i; 
    int max_ending_here[size]; 
    int sum_from_here[size]; 

    max_ending_here[0] = a[0]; 
    //sum_from_here[0] = a[0] + a[1]; 

    for (i = 1; i < size; i++) 
    { 
     max_ending_here[i] = max_ending_here[i-1] + a[i]; 
     sum_from_here[i] = a[i-1] + a[i]; 

     if (max_so_far < (max_ending_here[i] + sum_from_here[i])) 
      max_so_far = max_ending_here[i] + sum_from_here[i]; 

    } 

    return max_so_far; 
} 

/*Driver program to test maxSubArraySum*/ 
int main() 
{ 
    int a[] = { -2, 3, 4, -5, 9, -13, 100, -101, 7 }; 
    int n = sizeof(a)/sizeof(a[0]); 
    int max_sum = maxSubArraySum(a); 
    printf("Maximum contiguous sum is %d\n", max_sum); 
    getchar(); 
    return 0; 
} 

Answer 1

подход:

1. Пусть max_ending_here быть массив, элемент которой max_ending_here[i] обозначает максимальную сумму подмассивов (может быть пустым), который заканчивается как раз перед (не включены) индекс i. Чтобы вычислить его, используйте тот же подход, что и в вашей функции maxSubArraySum. Сложность времени - O(n), а сложность пространства - O(n).

2. Пусть sum_from_here быть массив, чей элемент sum_from_here[i] обозначает сумму в длину 2-подрешетке, начиная с (включительно) индекса i, что означает sum_from_here[i] = a[i] + a[i + 1]. Сложность времени - O(n), а сложность пространства - O(n).

3. Истерируйте все допустимые индексы и найдите максимальное значение max_ending_here[i] + sum_from_here[i]: это значение является тем, что вы ищете. Сложность времени - O(n), а сложность пространства - O(1).

Таким образом, общая сложность времени O(n) и сложность пространство O(n).

Этот подход расширяется до произвольной минимальной длины - не только 2, а время & космическая сложность не растет.

Ваш оригинальный реализовать в maxSubArraySum на самом деле является частным случаем такого подхода выше, в котором минимальная длина подмассив 0.

Редакцией:

Согласно кодексу вы обеспечиваете в обновлении 1, I сделали несколько изменений и представить правильную версию здесь:

int maxSubArraySum(int a[]) 
{ 
    int max_so_far = 0; 
    int i; 
    int max_ending_here[size]; 
    int sum_from_here[size]; 

    max_ending_here[0] = 0; 
    for (i = 1; i < size - 1; i++) 
    { 
     max_ending_here[i] = max_ending_here[i - 1] + a[i - 1]; 
     if (max_ending_here[i] < 0) 
      max_ending_here[i] = 0; 
     sum_from_here[i] = a[i] + a[i + 1]; 

     if (max_so_far < (max_ending_here[i] + sum_from_here[i])) 
      max_so_far = max_ending_here[i] + sum_from_here[i]; 

    } 

    return max_so_far; 
} 

Обратите внимание на ключе max_ending_here[i] и sum_from_here[i] не должны более круг. Вот пример:

-2 3 4 -5 9 -13 100 -101 7 
    | 3 4 -5 9 | -13 100 | 
      |    | 
      |    | 
      this   | 
      is    | 
    max_ending_here[5] | 
          | 
         this 
          is 
        sum_from_here[5] 

Answer 2

Вы можете решить эту проблему с помощью алгоритма скользящего окна, который я реализовал here.

Во всех точках, в ходе алгоритма мы поддерживаем следующие

1. ОКНО [се ... привет].
2. Сумма текущего окна.
3. Переменная, называемая индексом, которая отслеживает неудачный префикс в текущем окне, удаляя, что увеличит значение суммы. Поэтому, если мы удалим префикс [lo ... index], новое окно станет [index + 1 ... hi], и сумма будет возрастать по мере того, как индекс [lo ... index] имеет отрицательную сумму.
4. Сумма префикса, хранящегося в префиксе переменнойSum. Он содержит сумму для интервала [lo ... index].
5. The bestSum, который был найден до сих пор.

Initialize

• окно = [0 ... 1]
• сумма = обр [0] + обр 1
• индекс = 0
• prefixSum = обр [0]

Теперь на каждой итерации цикла while,

• Проверить, если префикс существует в текущем окне удаления, которое увеличит значение суммы
• добавить следующее значение в списке на текущий интервал и изменить окна и суммовые переменные.
• Обновить переменную bestSum.

Следующий working Java code реализует выше объяснение.

 int lo = 0; 
     int hi = 1; 
     int sum = arr[0] + arr[1]; 
     int index = 0; 
     int prefixSum = arr[0]; 

     int bestSum = sum; 
     int bestLo = 0; 
     int bestHi = 1; 

     while(true){ 
      // Removes bad prefixes that sum to a negative value. 
      while(true){ 
       if(hi-index <= 1){ 
        break; 
       } 
       if(prefixSum<0){ 
        sum -= prefixSum; 
        lo = index+1; 
        index++; 
        prefixSum = arr[index]; 
        break; 
       }else{ 
        prefixSum += arr[++index]; 
       } 
      } 

      // Update the bestSum, bestLo and bestHi variables. 
      if(sum > bestSum){ 
       bestSum = sum; 
       bestLo = lo; 
       bestHi = hi; 
      } 

      if(hi==arr.length-1){ 
       break; 
      } 

      // Include arr[hi+1] in the current window. 
      sum += arr[++hi]; 
     } 
     System.out.println("ANS : " + bestSum); 
     System.out.println("Interval : " + bestLo + " to " + bestHi); 

Во всех точках во время алгоритма ло + 1 = < привет и на каждом шаге цикла в то время как мы увеличиваем привет на 1. Кроме того ни переменная ло ни индекс никогда не уменьшится , Следовательно, временная сложность линейна по размеру ввода.

Временная сложность: O(n)
Space Сложность: O(1)