LeetCode --- 53. Maximum Subarray

タイトルリンク:Maximum Subaray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
この問題の要求は配列と最大の連続サブ配列を見つけることである.練習を広げて、分治して問題を解決してみてください.もっと面白いですよ.
1.動的計画
非常に一般的なダイナミックプランニングの問題であり、入門レベルの簡単なダイナミックプランニングでもあります.i要素を含むサブ配列の最大和をmaxl[i]配列で表すと、動的計画の繰返し式は、maxl[i+1]=max(maxl[i]+A[i],A[i+1])であり、最大値は配列の現在の要素と配列の現在の要素と前の結果の和の最大値であるに違いない.次に、問題全体の最大値はmaxl配列の最大値です.
しかしながらmasl[i]は前の結果のみを用いたため、実際の処理ではcur変数で現在の要素を含む最大値を維持し、resで最後の最大値を維持することができる.するとcur=max(cur+A[i],A[i]),res=max(res,cur)となる.
時間複雑度:O(n)
空間複雑度:O(1)

 1 class Solution
 2 {
 3 public:
 4     int maxSubArray(int A[], int n)
 5     {
 6         int res = A[0], cur = A[0];
 7         for(int i = 1; i < n; ++ i)
 8         {
 9             cur = max(cur + A[i], A[i]);
10             res = max(res, cur);
11         }
12         return res;
13     }
14 };

2.分けて治める
問題は解決したが,次の展開,すなわち分治解決を発見した.分治といえば,現在の最大値は左側最大値と右側最大値のうち大きい値に等しいと考えられる.しかし、少し問題がありますが、この最大値は左右にまたがっている可能性もあるでしょう...
そこで,両側のサブ問題を扱う際には,最左端要素を含む最大値(lres)と最右端要素を含む最大値(rres)を同時にそれぞれ計算する必要がある.これにより、現在の最大値は、「左側最大値(res 1)」、「右側最大値(res 2)」、「左側最右端要素を含む最大値(rres 1)および右側最左端要素を含む最大値(lres 2)の和」の3つである.
一方、lresは左側のみと右側も含む2つのケースに分けられます.

左側の左端要素を含む最大値(lres 1)

左側要素の和に右側の左端要素を含む最大値(all 1+lres 2)

を加える
最右端要素を含む最大値は、lres=max(lres 1,all 1+lres 2)およびrres=max(rres 2,all 2+rres 1)である.
問題が解決される.時間の複雑さについては,個人的にはn/2+n/4+n/8+...=O(n).
時間複雑度:O(n)
空間複雑度:O(1)

 1 class Solution
 2 {
 3 public:
 4     int maxSubArray(int A[], int n)
 5     {
 6         int res, lres, rres, all;
 7         maxSubArray(A, 0, n - 1, res, lres, rres, all);
 8         return res;
 9     }
10 private:
11     void maxSubArray(int A[], int l, int r, 
12                      int &res, int &lres, int &rres, int &all)
13     {
14         if(l == r)
15         {
16             res = lres = rres = all = A[l];
17             return;
18         }
19 
20         int m = (l + r) / 2;
21         int res1, lres1, rres1, all1, res2, lres2, rres2, all2;
22 
23         maxSubArray(A, l, m, res1, lres1, rres1, all1);
24         maxSubArray(A, m + 1, r, res2, lres2, rres2, all2);
25 
26         res = max(max(res1, res2), rres1 + lres2);
27         lres = max(lres1, all1 + lres2);
28         rres = max(rres2, all2 + rres1);
29         all = all1 + all2;
30     }
31 };

転載は出典:LeetCode---53.Maximum Subarray