---
# System prepended metadata

title: 'Leetcode [No. 53] Maximum Subarray (MEDIUM)'
tags: [leetcode]

---

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

## 題目

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

## 思路
+ 這個解法應該是我想得到的解中最快的解了
+ 就是去iterate每一個element後去記錄當前的最高sum跟連續sum
+ 接著隨時去更新maxSum 最後去return
```c++=
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)


### 執行結果
![image](https://hackmd.io/_uploads/S1V5SLNOT.png)



---

## NeetCode150 Practice on 2025/06/21

+ Easy Greedy

```c++=
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;
    }
};

```

![image](https://hackmd.io/_uploads/BypRR14Nll.png)
