# **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://www.youtube.com/watch?v=5WZl3MMT0Eg
Provided by. NeetCode
###### tags: `dynamic programming` `medium` `leetcode` `值得再想`
Sign in with Wallet
Connect another wallet