LeetCode 53. Maximum Subarray

Problem:

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.

Solution:

DP

public class Solution {
    int[] end;
    public int maxSubArray(int[] nums) {
        end = new int[nums.length];
        if (nums.length < 2) return nums[0];
        end[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int connect = end[i-1] + nums[i];
            int alone = nums[i];
            end[i] = connect > alone ? connect : alone;
        }
        int max = end[0];
        for (int i = 1; i < nums.length; i++) {
            if (end[i] > max) max = end[i];
        }
        return max;
    }
}

One thought on “LeetCode 53. Maximum Subarray”

Leave a Reply

Your email address will not be published. Required fields are marked *