# Leetcode [No. 53] Maximum Subarray (MEDIUM)

## 題目

https://leetcode.com/problems/maximum-subarray/description/

## 思路
+ 這個解法應該是我想得到的解中最快的解了
+ 就是去iterate每一個element後去記錄當前的最高sum跟連續sum
+ 接著隨時去更新maxSum 最後去return

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int prevSum = nums[0];
        int maxSum = nums[0];
        for(int i = 1 ; i < nums.size(); i++)
        {
            if(prevSum + nums[i] > nums[i])
            {
                prevSum += nums[i];
            }
            else
            {
                prevSum = nums[i];
            }
            maxSum = max(prevSum, maxSum);
            // cout << maxSum << "\t";
        }
        return maxSum;
    }
};

### 解法分析
+ time complexity: O(n)

### 執行結果

---

## NeetCode150 Practice on 2025/06/21

+ Easy Greedy

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int curSum = 0;
        int maxSum = INT_MIN;
        for (auto num: nums) {
            if (curSum < 0 && curSum < num) {
                curSum = num;
            } else {
                curSum += num;
            }
            maxSum = max(maxSum, curSum);
        }
        return maxSum;
    }
};