Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

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

Input: nums = [1] Output: 1 Explanation: The subarray [1] has the largest sum 1. Example 3:

Input: nums = [5,4,-1,7,8] Output: 23 Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

<解題>

1. 將 currentSum 設置為 nums[i] 和 currentSum + nums[i] 中的較大值。這樣做的原因是，我們要判斷是要將當前元素納入子數組，還是重新開始一個新的子數組。
2. 同時，將 maxSum 設置為 maxSum 和 currentSum 中的較大值。這是為了確保我們總是在整個過程中保留最大的子數組和。

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];

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

        return maxSum;
    }
}

Time: O() Space: O()