【LeetCode】 53. Maximum Subarray 最大子序列和

古城微笑少年丶 2022-06-13 23:15 285阅读 0赞

原题

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`.

思路

1. 最笨的办法

> 用2个for循环，遍历所有的子序列和，最后得到其中最大的一个
> 
>  
> 
>     public class Solution {
>         public int maxSubArray(int[] nums) {
>             int max = nums[0];
>             int len = nums.length;
>             int tempSum = 0;
>             for(int i = 0 ; i< len ;i ++){
>                 tempSum = nums[i];
>                 if(tempSum >max){
>                     max = tempSum;
>                 }
>                 for(int j = i+1; j< len; j++){
>                     tempSum += nums[j];
>                     if(tempSum >max){
>                         max = tempSum;
>                     }
>                 }
>             }
>             return max;
>         }
>     }
> 
>   
> 时间复杂度O(n^2) 
> 
>

2. 经典的DP  
  
  
对一个序列\[a1, a2, a3, ..., an\]，要求最大子序列和，可以等价于求max(以a1为起点的序列的最大序列和，以a2为起点的序列的最大和，...，以an为起点的序列的最大和)。而对于第i项ai，不难推出，以ai为起点的序列最大和为：  
max\_sum(i) = max(ai, max\_sum(i+1) + ai)  
然后递推出max\_sum(1)，也就是最后的结果了。  
  
  
依此，我们可以写一个for循环，从数组的最后往前，依次递推，并保存最大值：

public int maxSubArray(int[] nums) {
                int max = nums[nums.length - 1];
                int lastMaxSum = nums[nums.length - 1];
    
    
                for (int i = nums.length - 2; i >= 0; i--) {
                    int ai = nums[i];
                    lastMaxSum = lastMaxSum > 0 ? ai + lastMaxSum : ai;
                    max = Math.max(max, lastMaxSum);
                }
                return max;
            }

时间复杂度O(n)

## 更新： ##

某日夜，突然想到这道题，灵光一现，特此记录。

1. 记数列\{a\[0\], a\[1\] ... a\[n\]\} = S\[n\]，那么：

对于数列S\[n\]，若其最大子序列和为S，有：

S = S\[q\] - S\[p-1\]

则原问题化为\{S\[0\], S\[1\] .. S\[n\]\}找最大差值（后-前）的问题。

即原问题等价于对于任意0≤p≤q≤n，求S\[q\] - S\[p\]的最大值。

2. 易证：

S\[p-1\] = min\{S\[0\] .. S\[q\]\}

S\[q\] = max\{S\[p\] .. S\[q\]\}

则原问题化为求阶段性最小值、最大值的问题。

3. 经过1和2的转化，问题已经很简单了。

对于正整数 i ∈\[0, n\]，最大子序列和 maxSubarr\[i\] = Sum2 - Sum1。其中：

Sum1 为 S\[0\] ~ S\[i\] 的最小值，Sum2 为 S\[x\] ~ S\[i\] 的最大值。

代码：

public int maxSubArray(int[] nums) {
                int sumTmp; // = S[0, i]
                int minTmp; //记录阶段性的最小值
                int maxTmp; //记录阶段性的最大值
                int max; // 最大序列和
                boolean allNeg = true; // 特殊情况，如果所有都是负数
                minTmp = maxTmp = sumTmp = max = nums[0];
    
                for (int ai : nums) {
                    sumTmp += ai; // = S[0, i]
                    if (allNeg) {
                        if (max < ai) max = ai;
                        if (ai >= 0) allNeg = false;
                    }
                    if (sumTmp < minTmp) {
                        minTmp = maxTmp = sumTmp; // 新的阶段最小值
                    } else if (sumTmp > maxTmp) {
                        maxTmp = sumTmp; // 新的阶段最大值
                        int diff = sumTmp - minTmp;
                        if (diff > max) {
                            max = diff; // 判断是否是最大差值
                        }
                    }
                }
                return max;
            }

这个方法的思路，是把一个复杂的问题等价转化为另一个简单的问题。虽然代码反而变多了，但是思考层级变低了，就好似把一道高等数学的题目用初等数学的方法解决（小学教材求圆的面积）。我觉得还是有一定的记录价值的。