なぜ最大合計サブアレイはブルートフォースO（n^2）ですか？

Question

maximum subarray sumは、コンピュータサイエンスの有名な問題です。

少なくとも二つの解決策があります

1. ブルート力は、すべての可能なサブ配列を検索し、最大値を見つけます。
2. Karanes Algorithmのバリエーションを使用して、配列の最初のパスを通過する際にグローバルmaxを計算します。ビデオで

tutorial著者は強引な方法がO(n^2)で言及し、another answer 1人が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

最大サブアレイ和問題に対する3つの解法である。 solve1()はO（N）時間で実行され、solve2()はO（N^2）で実行され、solve3()はO（N^3）で実行されます。 solve1()は、Kadaneのアルゴリズムとして知られています。

O（N^2）関数とO（N^3）関数の違いは、endのインデックスがインクリメントされるたびに合計が暗黙的に計算されることです。 O（N^3）関数の場合、和はstartとendの間の3番目の明示的なループで計算されます。

すべての入力値が負である場合に、この3つの方法を処理するコードを追加しました。

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); 
    } 
} 

出力は次のとおりです。

質問に記載されているKadaneのアルゴリズムは、だ

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