Maximum Subarray

还是做得复杂了一点，跟上一道sliding window的问题一样
不需要先把整个array扫一遍记录一个PrefixSum的数组，只需要维持一个int PrefixSum就可以了
像这种从左向右扫一遍的题，都不需要提前做好数组。

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        // write your code
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] prefixSum = new int[nums.length + 1];
        prefixSum[0] = 0;
        for (int i = 1; i < prefixSum.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }
        int prevMinSum = prefixSum[0];
        int maxSum = prefixSum[1];
        for (int j = 1; j < prefixSum.length; j++) {
            prevMinSum = Math.min(prevMinSum, prefixSum[j - 1]);
            maxSum = Math.max(maxSum, prefixSum[j] - prevMinSum);
        }
        return maxSum;
     
    }
}