Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

In order to solve this, we will use prefix-sums. So we just calculate all elements of prefix-sum array (PS) (first element of PS = first element, second element of PS = first element of PS + second element, third element of PS = second element of PS + third element…). Then we get this array:

In order to find maximum subarray, we go element by element of PS array, and subtract from minimal element on the left side (we have to track what is current min element on the left side of the pointer – pointer points to current element of PS we examine right now). This guarantees to find maximum subarray from left side to current element that we examine.

 public class Solution {
    public int maxSubArray(int[] nums) {
        int min = 0;
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for(int i : nums){
            sum += i;
            max = Math.max(sum-min, max);
            min = Math.min(sum, min);
        }
        return max;
    }

    public static void main(String[] args) {
        //100
        System.out.println(new Solution().maxSubArray(new int[]{1,2,3,4,-105,100,-105,10,5}));
        //6
        System.out.println(new Solution().maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
        //-1
        System.out.println(new Solution().maxSubArray(new int[]{-2,-1}));
    }
}

or simplified:

public int maxSubArray(int[] nums) {

        int globalMax=nums[0];
        int currentMax=nums[0];

        for(int i=1;i<nums.length;i++){
            currentMax = Math.max(nums[i]+currentMax,nums[i]);
            globalMax = Math.max(currentMax,globalMax);
        }

        return globalMax;
    }