Note:

define: Sum[i] means the maximum sum in front of i elements

public int maxSubArray(int[] nums){   //O(n)
        //DP
        /*if(nums == null || nums.length == 0){
            return 0;
        }
        int[] max = new int[nums.length];
        int[] sum = new int[nums.length];

        max[0] = nums[0];
        sum[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            sum[i] = Math.max(nums[i], sum[i - 1] + nums[i]);
            max[i] = Math.max(max[i - 1], sum[i]);
        }
        return max[nums.length - 1];*/






        //Save DP space
        //define: Sum[i] means the maximum sum in front of i elements
        if(nums == null || nums.length == 0){
            return 0;
        }

        int[] sum = new int[2];
        int[] max = new int[2];

        //initial
        sum[0] = nums[0];
        max[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            sum[i % 2] = Math.max(nums[i], sum[(i - 1) % 2] + nums[i]);
            max[i % 2] = Math.max(max[(i - 1) % 2], sum[i % 2]);
        }

        return max[(nums.length - 1) % 2];
    }