Example: MaxSubArray - rFronteddu/general_wiki GitHub Wiki

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Also known as Kadane's Algorithm

Better solution that does not modify input array

class Solution {
    public int maxSubArray(int[] nums) {  
        int maxSum = nums[0];
        int p = nums[0];
        for (int i = 1; i < nums.length; i++) {
            p = Math.max(p + nums[i], nums[i]);
            maxSum = Math.max(maxSum, p);
        }
        return maxSum;
    }
}

Old solution

class Solution {
    public int maxSubArray(int[] nums) {        
        int maxSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            nums[i] = Math.max(nums[i], nums[i] + nums[i-1]);
            maxSum = Math.max(nums[i], maxSum);
        }
        return maxSum;
    }
}