class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] sums = new int[n];
        sums[0] = nums[0];

        int ans = sums[0];
        for (int i = 1; i < n; i++){
            sums[i] = Math.max(nums[i], nums[i] + sums[i - 1]);
            ans = Math.max(ans, sums[i]);
        }

        return ans;
    }
}