53. Maximum Subarray

三刷 07/2022

Version #3 Kadane's Algorithm

If the previous subarray sum is larger than zero, it's always nice to add the previous subarray sum

It calculates the maximum sum subarray ending at a particular position by using the maximum sum subarray ending at the previous position.

Time O(N)

Space O(1)

class Solution {

    public int maxSubArray(int[] nums) {

        int max = Integer.MIN_VALUE;

        int prevMax = 0;

        for (int i = 0; i < nums.length; i++) {

            int currMax = nums[i] + (prevMax > 0 ? prevMax : 0);

            prevMax = currMax;

            max = Math.max(max, currMax);

        }

        return max;

    }

}

二刷
Version #3
99.93 %
定义currMax为以当前nums[i]为结尾的最大的subArraySum
如果之前的sum为负， 就不加，只算当前nums[i]自己
但凡之前的sum为正，就加当前nums[i]上
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException();
        }
        int globalMax = Integer.MIN_VALUE;
        int currMax = 0;
        // max end with nums[i]
        for (int i = 0; i < nums.length; i++) {
            currMax = (currMax > 0 ? currMax : 0) + nums[i];
            globalMax = Math.max(globalMax, currMax);
        }
        return globalMax;
    }
}



Version #1 DP
三刷
56.95 %
class Solution {
    public int maxSubArray(int[] nums) {
        // dp[i] = max sub array sum end with nums[i]
        // dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]) -> nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0)
        if (nums == null || nums.length == 0) return 0;
        int prev = nums[0];
        int max = prev;
        for (int i = 1; i < nums.length; i++) {
            int curr = (prev > 0 ? prev : 0) + nums[i];
            max = Math.max(max, curr);
            prev = curr;
        }
        return max;
    }
}

一刷
78.03 %
需要注意因为初始化的是dp[0]
for loop是从index == 1开始的
所以要在一开始把max赋值为dp[0]
否则它没有机会与max进行比较

public class Solution {
    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0){
            return 0;
        }
        int[] dp = new int[2];
        // dp[0] dp[1] dp[0] dp[1]...
        //[-2,    1,    -3,   4,   -1,2,1,-5,4]
        dp[0] = A[0];
        int max = dp[0];
        for (int i = 1; i < A.length; i++) {
            if (dp[(i - 1) % 2] > 0) dp[i % 2] = dp[(i - 1) % 2] + A[i];
            else dp[i % 2] = A[i];
            max = Math.max(max, dp[i % 2]);
        }
        return max;
    }
}

Version #2 Prefix sum
94.74 %
Find the most difference between prefix sum at index i and the minimum prefix sum before it
public class Solution {
    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0){
            return 0;
        }
   
        int max = Integer.MIN_VALUE, sum = 0, minSum = 0;
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            max = Math.max(max, sum - minSum);
            minSum = Math.min(minSum, sum);
        }

        return max;
    }
}