---
# System prepended metadata

title: '**Leetcode筆記(Maximum Subarray)**'
tags: [值得再想, medium, dynamic programming, leetcode]

---

# **Leetcode筆記(Maximum Subarray)**


:::info
:information_source: 題目 : Maximum Subarray, 類型 : dynamic programming , 等級 : medium
日期 : 2023/02/17，2023/06/12，2023/07/21，2023/09/24，2023/11/30，2024/11/18
:::


### 嘗試

想要從一個array的max下去找，從max左右擴散

```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        record = {}
        for i, val in enumerate(nums):
            record[val] = i
            max1 = val
            realmax = max(max1, realmax)
            maxindex = record[val]
        for i in range(maxindex,len(nums)):
            realmax = nums[i]
```
2023/06/12
greedy法
要找的可能是當下這個數字本身，或是從前面累加的其他數字
如果累加過的數字比現在這個數字單獨的還大，那最優解一定是累加的

例如nums = [-2,1,-3,4,-1,2,1,-5,4]
例如[-2, 1]就是1，一定會跳過-2
[-2, 1, -3]就是-2，[-2, 1, -3, 4]就是4
```python
公式 cur = max(nums[i], cur + nums[i])

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = nums[0]
        cur = 0

        for n in nums:
            cur = max((cur + n), n)
            res = max(res, cur)
        
        return res
```
2023/07/21
想要維持一個連續的subarray，有兩個選擇
1. 前面所有數字 + 當前的數字
2. 捨棄前面數字，只從當前數字開始
```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        tmp, res = 0, float("-inf")

        for n in nums:
            tmp = max(tmp + n, n)
            res = max(res, tmp)
        
        return res
```
2023/09/24
今天更驗證leetcode這種東西是需要複習的，這題我寫了四次，但今天還是沒有很清晰的頭緒阿
1. 只選現在這個n
2. 包含累加的前面所有 + 現在這個n
```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res, temp = float("-inf"), 0
        # 1. choose the (previous + current n)
        # 2. choose the current n
        for n in nums:
            temp = max(temp + n, n)
            res = max(res, temp)
        
        return res
```
2023/11/30
```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        i = 0
        res = nums[0]
        n = 0

        while i < len(nums):
            n += nums[i]
            res = max(res, n)
            if n < 0:
                n = 0
            i += 1
        
        return res
```

2024/11/18
```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        self.res = float("-inf")
        r = 0
        total = 0
        while r < len(nums):
            total += nums[r]
            self.res = max(self.res, total)
            if total <= 0:
                total = 0
            r += 1
        
        return self.res
```


---
### **優化**

從左到右掃過去，若是算出來是負數，則必定拋棄，若一直為正，則往右邊相加，並比較誰大。時間複雜度O(n)，不用任何額外記憶體

```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSub = nums[0]
        sumSub = 0
        for n in nums:
            if sumSub < 0:
                sumSub = 0
            sumSub = sumSub + n
            maxSub = max(maxSub, sumSub)
        return maxSub
```
---


**:warning: 錯誤語法** 
:::warning
注意在此題，maxSub和sumSub都是全域變數
:::


**:thumbsup:學習** 
:::success
maxSub = nums[0] -> 直接把nums[0]當成記憶體媒介
A subarray is a contiguous non-empty sequence of elements within an array.
:::

**思路**
![](https://i.imgur.com/iCBB4B8.png)

**講解連結**
https://www.youtube.com/watch?v=5WZl3MMT0Eg
Provided by. NeetCode

###### tags: `dynamic programming` `medium` `leetcode` `值得再想`