Problem :

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. 累加並儲存子陣列中的和並儲存陣列中的最大值
2. 遍歷尋找陣列中最大的元素並更新最大元素
3. 若陣列中的和為陣列中的唯一元素，則將最大和設為陣列中的唯一元素並回傳
4. 遍歷尋找最大子陣列的和，若當前的和小於０則將和歸零並重新開始新的子陣列，若當前的最大和大於目前的最大和，則更新最大和
5. 回傳最大子陣列的和

程式碼 :

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //累加當前子陣列的和
        int sum = 0;
        //儲存最大子陣列的和
        int max = 0; 
        //儲存陣列中的最大值
        int temp = INT_MIN;
        //遍歷尋找陣列中最大的元素
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] > temp){
                //更新最大元素
                temp = nums[i];
            }
        }
        //若陣列中最大的元素小於0則回傳該元素
        if(temp < 0){
            //將最大和設為陣列中唯一的元素
            max = temp;
            //回傳陣列中的元素
            return max;
        }
        //遍歷尋找最大子陣列的和
        for(int i = 0; i < nums.size(); i++){
            sum += nums[i];
            //若當前的和小於0，則歸零重新開始新的子陣列
            if(sum < 0){
                sum = 0;
            }
            //若當前的和大於最大和，則更新最大和
            if(sum > max){
                max = sum;
            }
        }
        //回傳最大子陣列的和
        return max;
    }
};

結論 :

這題的目標是尋找陣列中最大子陣列的和，透過尋找最陣列中的元素來處理所有元素為負數的狀況，也透過累加當前子陣列中的和來尋找最大子陣列的和並再必要時進行重置以尋找新的子陣列，這段程式碼的時間複雜度Ｏ(n)。