原文題目

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

• Subarray: A subarray is a contiguous non-empty sequence of elements within an array.

題目摘要

1. 題目描述：給定一個整數陣列 nums，找出其中連續子陣列（至少包含一個元素）之和的最大值，並回傳該最大值。
2. 輸入：一個整數陣列 nums，長度為 n，其中 n ≥ 1。
3. 輸出：該陣列中連續子陣列的最大和。

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. 定義最大和與當前和：

   • 我們將 maxSum 和 currentSum 都初始化為陣列的第一個元素。這是因為至少有一個元素必須被包含在子陣列中，且陣列不為空。

2. 遍歷陣列：

   從第二個元素開始（即 i = 1），對每個元素，我們需要決定：

   • 是否將這個元素加入當前的子陣列和中（即 currentSum + nums[i]），
   • 還是從這個元素重新開始一個新的子陣列（即 nums[i]）。透過 currentSum = Math.max(nums[i], currentSum + nums[i]) 來更新當前子陣列的和。

3. 更新最大和：

   • 每次更新完 currentSum 後，檢查它是否比 maxSum 大。如果是，就更新 maxSum。這樣，當我們遍歷完整個陣列後，maxSum 就會保存全局最大子陣列的和。

程式碼

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;  //回傳最大子陣列和
    }
}

結論： 這題的最大子陣列問題，其實有點像我們在人生中面對挑戰時的抉擇。你可以選擇把每個困難（負數）繼續累積下去，或是乾脆從新的起點重新開始（拋棄負面情緒）。這就像是告訴你：「如果當下的狀況拖累了你，那就從現在開始重頭來過。」這個解法中，我們不斷在更新當前最佳狀態，並時時反思是否需要重新出發，這不正是我們處理問題的最佳策略嗎？這題不只教會我們如何在程式中找最大值，也像是提醒我們生活中面對挑戰時保持彈性和勇氣。