# 53. Maximum Subarray

## 題目概要
在 nums 整數陣列中找出總和最大的連續子陣列(最少要有一個元素)，並返回最大值。

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 = [1]
Output: 1

Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23

## 解題技巧
- 可以使用貪婪演算法(Greedy algorithm)或動態規劃(Dynamic programming)來解。

## 程式碼

### 貪婪演算法

用 for 循環遍歷一個一個元素慢慢往下加，然後將總和跟當前最大值比較，將比較大的值存下來。一旦當前的數小於 0 的時候就將當前總和歸零，繼續找下一個子陣列。

PS. 注意 max 一定要預設為 -Infinity，因為總和會有負數，如果設為 0 會是錯的。

var maxSubArray = function(nums) {
    let max = -Infinity; // 當前最大子序列的總和
    let sum = 0; // 當前總和
    for(let i = 0; i < nums.length; i++) {
        sum += nums[i];
        max = Math.max(max, sum);
        
        if (sum < 0) sum = 0;
    }
    
    return max;
};


### 動態規劃
我們可以從第一個元素開始慢慢找，看包含第一個元素加第二個元素及第二個元素本身的總和哪個大，就選哪個繼續往下做，比如有一陣列為 [-2,1,-3,4,-1,2,1,-5,4]：

1. [-2, 1] 和 [1] 相比 -2 + 1 = -1 < 1，所以 [1] 較大，直接跳過 -2，將 [1] 設為最大子序列起始繼續往下
1. [1, -3] 和 [-3] 是 1 – 3 = -2 > -3，所以將 [1, -3] 繼續往下
1. [1, -3, 4] 和 [4] 是 4 比較大，所以拋棄 [1, -3]，以 [4] 為最大子序列起始再往下做
1. [4, -1] 和 [-1] 相比 4 – 1 = 3 > -1，所以將 [4, -1] 繼續往下
1. [4, -1, 2] 和 [2] 相比 4 – 1 + 2 = 5 > 2 所以將 [4, -1, 2] 繼續往下
1. [4, -1, 2, 1] 和 [1] 相比 4 – 1 + 2 + 1 = 6 > 1 所以將 [4, -1, 2, 1] 繼續往下
1. [4, -1, 2, 1, -5] 和 [-5] 相比 4 – 1 + 2 + 1 – 5 = 1 > -5 所以將 [4, -1, 2, 1, -5] 繼續往下
1. [4, -1, 2, 1, -5, 4] 和 [4] 相比 4 – 1 + 2 + 1 – 5 + 4 = 5 > 4 ，全部元素比較結束。
在這段遍歷中，我們可以得知 [4, -1, 2, 1] 這段子序列的總和是最大的，為 6，所以答案為 6。

比較核心的公式為： `Math.max(arr[i - 1] + nums[i], nums[i]);`

這裡面的 `arr[i]` 代表包含第幾個元素的最大值。

var maxSubArray = function(nums) {
    let arr = [];
    arr[0] = nums[0]; // 子序列必須至少包含一個元素
    let max = arr[0];

    for(let i = 1; i < nums.length; i++) {
        arr[i] = Math.max(arr[i - 1] + nums[i], nums[i]);
        max = Math.max(arr[i], max);
    }

    return max;
};

有點難用文字說明，還是看程式碼最快。