Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

• Time: O(n)
• Space: O(1)

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