Почему максимальная суммарная субармальная грубая сила O (n^2)?

Question

maximum subarray sum - известная проблема в информатике.

Есть по крайней мере два решения:

1. перебор, найти все возможные вложенные массивы и найти максимум.
2. Используйте переменную Karanes Algorithm для вычисления глобального максимума при прохождении первого прохода массива.

В видео tutorial автор упоминает метод грубой силы O(n^2), чтение another answer один человек думает, что это O(n^2), а другой думает, что это O(n^3)

ли перебором O(n^2) или O(n^3)? И что еще более важно, можете ли вы проиллюстрировать, какой анализ вы выполнили по методу грубой силы, чтобы знать, что это O(?)?

Answer 1

Ну, это зависит от того, насколько грубой является сила.

Если мы генерируем все (i, j): i <= j пары и вычислить сумму между ними, это O(n^3):

.... 
for (int i = 0; i < n; i++) 
    for (int j = i; j < n; j++) { 
     int sum = 0; 
     for (int k = i; k <= j; k++) 
      sum += a[k]; 
     if (sum > max) 
      max = sum; 
    } 

Если мы начнем на всех позициях и вычислить работы суммы, это O(n^2):

.... 
for(int i = 0; i < n; i++) { 
    int sum = 0; 
    for (int j = i; j < n; j++) { 
     sum += a[j]; 
     if (sum > max) 
      max = sum; 
    } 
} 

Answer 2

Это можно сделать с помощью O (N), как показано ниже! Я что-то упустил?

int[] arr = {}; //elements; 
    int max = 0, temp = 0; 
    for (int i = 0; i < arr.length; i++) { 
     temp = Math.max(arr[i], arr[i] + temp); 
     max = Math.max(temp, max); 
    } 
    System.out.println(max); //result 

Answer 3

Здесь являются тремя решениями задачи суммарной суммарной суммы субарах. solve1() работает в O (N) времени, solve2() работает в O (N^2), а solve3() работает в O (N^3). Обратите внимание, что solve1() известен как алгоритм Кадане.

Разница между функциями O (N^2) и O (N^3) заключается в том, что в функции O (N^2) сумма вычисляется неявно каждый раз, когда индекс end увеличивается, а в O (N^3), сумма вычисляется с третьим явным циклом между start и end.

Я добавил код ко всем трем подходам, чтобы обрабатывать случай, когда все входные значения отрицательные.

public class MaximumSubarraySum { 

    /** 
    * Solves the maximum subarray sum in O(N) time. 
    */ 
    public static int solve1(int[] input) { 

     int sum = input[0]; 
     int bestSum = sum; 

     for (int i = 1; i < input.length; i++) { 
      sum = Math.max(input[i], input[i] + sum); 
      bestSum = Math.max(sum, bestSum); 
     } 

     return bestSum; 
    } 

    /** 
    * Solves the maximum subarray sum in O(N^2) time. The two indices 
    * 'start' and 'end' iterate over all possible N^2 index pairs, with 
    * the sum of input[start, end] always computed for every 'end' value. 
    */ 
    public static int solve2(int[] input) { 

     int bestSum = -Integer.MAX_VALUE; 

     for (int start = 0; start < input.length; start++) { 

      // Compute the sum of input[start, end] and update 
      // 'bestSum' if we found a new max subarray sum. 

      // Set the sum to initial input value to handle edge case 
      // of all the values being negative. 
      int sum = input[start]; 
      bestSum = Math.max(sum, bestSum); 

      for (int end = start+1; end < input.length; end++) { 
       sum += input[end]; 
       bestSum = Math.max(sum, bestSum); 
      } 
     } 

     return bestSum; 
    } 

    /** 
    * Solves the maximum subarray sum in O(N^3) time. The two indices 
    * 'start' and 'end' iterate over all possible N^2 index pairs, and 
    * a third loop with index 'mid' iterates between them to compute 
    * the sum of input[start, end]. 
    */ 
    public static int solve3(int[] input) { 

     int bestSum = -Integer.MAX_VALUE; 

     for (int start = 0; start < input.length; start++) { 

      for (int end = start; end < input.length; end++) { 

       // Compute the sum of input[start, end] using a third loop 
       // with index 'mid'. Update 'bestSum' if we found a new 
       // max subarray sum. 

       // Set the sum to initial input value to handle edge case 
       // of all the values being negative. 
       int sum = input[start]; 
       bestSum = Math.max(sum, bestSum); 

       for (int mid = start+1; mid < end; mid++) { 
        sum = Math.max(input[mid], input[mid] + sum); 
        bestSum = Math.max(sum, bestSum); 
       } 
      } 
     } 

     return bestSum; 
    } 


    public static void runTest(int[] input) { 

     System.out.printf("\n"); 
     System.out.printf("Input: "); 
     for (int i = 0; i < input.length; i++) { 
      System.out.printf("%2d", input[i]); 
      if (i < input.length-1) { 
       System.out.printf(", "); 
      } 
     } 
     System.out.printf("\n"); 

     int result = 0; 

     result = MaximumSubarraySum.solve1(input); 
     System.out.printf("solve1 result = %d\n", result); 

     result = MaximumSubarraySum.solve2(input); 
     System.out.printf("solve2 result = %d\n", result); 

     result = MaximumSubarraySum.solve3(input); 
     System.out.printf("solve3 result = %d\n", result); 

    } 


    public static void main(String argv[]) { 

     int[] test1 = { -2, -3, 4, -1, -2, -1, -5, -3 }; 
     runTest(test1); 

     int[] test2 = { -2, -3, -4, -1, -2, -1, -5, 3 }; 
     runTest(test2); 

     int[] test3 = { -2, -3, -4, -1, -2, -1, -5, -3 }; 
     runTest(test3); 

     int[] test4 = { -2, -3, 4, -1, -2, 1, 5, -3 }; 
     runTest(test4); 
    } 
} 

Выход:

Input: -2, -3, 4, -1, -2, -1, -5, -3 
solve1 result = 4 
solve2 result = 4 
solve3 result = 4 

Input: -2, -3, -4, -1, -2, -1, -5, 3 
solve1 result = 3 
solve2 result = 3 
solve3 result = 3 

Input: -2, -3, -4, -1, -2, -1, -5, -3 
solve1 result = -1 
solve2 result = -1 
solve3 result = -1 

Input: -2, -3, 4, -1, -2, 1, 5, -3 
solve1 result = 7 
solve2 result = 7 
solve3 result = 7