DAY 8
1
Software Development

## [Day 8] 從LeetCode學演算法 - 0053. Maximum Subarray (Easy)

``````Question:
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
``````
``````Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
``````
``````Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
``````

N+(N-1)+(N-2)+…+1，每個子陣列中的計算下一組和(如[-2] -> [-2,1])，

「假設我知道nums中1到i-1的最大子陣列和，

a. 這個子陣列包括index i
b. 這個子陣列不包括index i

1. 到現在為止包含當前這個元素的最大子陣列和，我們命名為curr(current)
2. 到目前為止的最大子陣列和，我們命名為res(result)

i=1: [-2,1,-3,4,-1,2,1,-5,4]

(註1: 表示兩者的正負號為(-, -), (-, +)，不論如何

)
(註2: 也可以拆成別的形式或調換順序，但先判斷<0的計算速度會比較快)
(註3: 後面程式碼Java和Python的判斷方式就不同，可自行依喜好決定使用)

``````i=2: [-2,1,-3,4,-1,2,1,-5,4]
-> curr = 1 + -3 = -2 < 0
-> curr = -3
-> res = 1

i=3: [-2,1,-3,4,-1,2,1,-5,4]
-> curr = -3 + 4 = 1 < 4
-> curr = 4
-> res = 4

i=4: [-2,1,-3,4,-1,2,1,-5,4]
-> curr = 4 + -1 = 3 > -1

i=5: [-2,1,-3,4,-1,2,1,-5,4]
-> curr = 3 + 2 = 5 > 2
-> res = 5

i=6: [-2,1,-3,4,-1,2,1,-5,4]
-> curr = 5 + 1 = 6 > 1
-> res = 6

i=7: [-2,1,-3,4,-1,2,1,-5,4]
-> curr = 6 + -5 = 1 > -5

i=8: [-2,1,-3,4,-1,2,1,-5,4]
-> curr = 1 + 4 = 5 > 4
``````

「N=i+1時的解，通常和N=i時的解以及第i+1的值有關連性」
(也有可能跟更前面幾個值同時有關連性)

Java:

``````class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
int curr = nums[0];
for(int i = 1; i < nums.length; i++) {
curr += nums[i];
if (curr < 0 || nums[i] > curr)
curr = nums[i];
if (res < curr)
res = curr;
}
return res;
}
}
``````

Python:

``````class Solution:
def maxSubArray(self, nums: 'List[int]') -> 'int':
l = len(nums)
if l == 0: return 0
res = now = nums[0]
for i in range(1, l):
if now > 0:
now += nums[i]
else:
now = nums[i]

if now > res:
res = now
return res
``````

「時間/空間複雜度？」
(O(N), O(1))

「如果不使用DP是否有O(N)解？」
(可以使用分治法，請參見 LeetCode這篇討論 底下的回應)