DAY 22
1
Software Development

## 53. Maximum Subarray

### 先看一下題目描述

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A subarray is a contiguous part of an array.

### 再搭配範例理解題目

• Example 1:
``````Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
``````
• Example 2:
``````Input: nums = [5,4,-1,7,8]
Output: 23
``````

## 開始實作

### 方法 ①：暴力法

#### 用 Python 實作一次

``````class Solution:
def maxSubArray(self, nums: List[int]) -> int:
m = float("-inf");
for i in range(len(nums)):
s = 0;
for j in range(i+1, len(nums)):
s += nums[j]
if s > m:
m = s
return m;
``````

#### 也可以用 JavaScript 復刻一次

``````var maxSubArray = function(nums) {
const len = nums.length;
let max = -Number.MAX_VALUE;
let sum = 0;
for (let i = 0; i < len; i++) {
sum = 0;
for (let j = i; j < len; j++) {
sum += nums[j];
if (sum > max) {
max = sum;
}
}
}
return max;
}
``````

### 方法 ②：累加法（Greedy）

``````[-2,1,-3,4,-1,2,1,-5,4]
``````

``````* -2
* 1
* -3
...
``````

``````* -2
* -2 + 1
* -2 + 1 + -3
* -2 + 1 + -3 + 4
* -2 + ...
``````
``````* 1
* 1 + -3
* 1 + -3 + 4
* 1 + ...
``````

#### 用 Python 實作一次

``````class Solution:
def maxSubArray(self, nums: List[int]) -> int:
maxSum = nums[0]
curSum = nums[0]
for num in nums:
curSum = max(curSum + num, num)
maxSum = max(maxSum, curSum)
return maxSum

``````

#### 也可以用 JavaScript 復刻一次

``````var maxSubArray = function(nums) {
var maxSum = nums[0],curSum = nums[0];
for(let num of nums){
curSum = Math.max(curSum + num, num);
maxSum = Math.max(maxSum, curSum);
}
return maxSum;
};
``````

### 方法 ③：累加法（DP）

#### 用 Python 實作一次

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

#### 也可以用 JavaScript 復刻一次

``````var maxSubArray = function(nums) {
let res = nums[0];
for (let i = 1; i < nums.length; ++i) {
if (nums[i - 1] > 0)
nums[i] += nums[i - 1];
res = Math.max(res, nums[i]);
}
return res;
};
``````