53. Maximum Subarray

題目：
給一個整數陣列 nums，找出連續子陣列（至少包含一個元素），使其總和最大，並回傳該最大總和

範例：

• 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.

想法：
從自己開始往後加，若為負則從新開始
——＞動態規劃（DP）+ 貪心思維

程式碼：

class Solution {
    public int maxSubArray(int[] nums) {
        int currentSum = nums[0];  // 當前子陣列的總和
        int maxSum = 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;
    }
}

實際操作：
輸入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
初始：currentSum = -2、maxSum = -2

Step1:
i = 1（num = 1）

• currentSum = max(1, -2 + 1) = 1
• maxSum = max(-2, 1) = 1

Step2:
i = 2（num = -3）

• currentSum = max(-3, 1 - 3) = -2
• maxSum = max(1, -2) = 1

Step3:
i = 3（num = 4）

• currentSum = max(4, -2 + 4) = 4
• maxSum = max(1, 4) = 4

Step4:
i = 4（num = -1）

• currentSum = max(-1, 4 - 1) = 3
• maxSum = max(4, 3) = 4

Step5:
i = 5（num = 2）

• currentSum = max(2, 3 + 2) = 5
• maxSum = max(4, 5) = 5

Step6:
i = 6（num = 1）

• currentSum = max(1, 5 + 1) = 6
• maxSum = max(5, 6) = 6

Step7:
i = 7（num = -5）

• currentSum = max(-5, 6 - 5) = 1
• maxSum = max(6, 1) = 6

Step8:
i = 8（num = 4）

• currentSum = max(4, 1 + 4) = 5
• maxSum = max(6, 5) = 6

答案：maxSum = 6
對應的最大子陣列為 [4, -1, 2, 1]