# 53. Maximum Subarray

### Leetcode

#### <https://leetcode.com/problems/maximum-subarray/description/>

### 題目

Given an integer array `nums`, find the subarray with the largest sum, and return *its sum*.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
</strong><strong>Output: 6
</strong><strong>Explanation: The subarray [4,-1,2,1] has the largest sum 6.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [1]
</strong><strong>Output: 1
</strong><strong>Explanation: The subarray [1] has the largest sum 1.
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [5,4,-1,7,8]
</strong><strong>Output: 23
</strong><strong>Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
</strong></code></pre>

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一 - 雙層迴圈暴力解**

第一層迴圈代表起始的那個數字，第二層迴圈去找出在起始數字固定下，有可能的最大加總值是多少

```javascript
var maxSubArray = function (nums) {
    let max = nums[0];

    for (let i = 0; i < nums.length; i++) {
        let sum = 0;
        for (let j = i + 1; j < nums.length; j++) {
            sum += nums[j];
            max = Math.max(max, accu);
        }
    }

    return max;
};
```

結果：Time Limit Exceeded

**參考資料**

{% embed url="<https://ithelp.ithome.com.tw/articles/10278815?sc=iThomeR>" %}

* **方法二 - Kadane's演算法**

Kadane's演算法，有人認為是貪婪算法，也有人認為是 DP 動態規劃，根據 [這篇文章](https://stackoverflow.com/questions/31155269/is-kadanes-algorithm-greedy-or-optimised-dp) 應該比較算是 DP

從動態規劃的方向思考：以陣列中的某個元素來看，到這個元素為止的子陣列，其加總的最大值會是多少呢？

核心公式是：

> **到某個元素為止的最大值** = "**自己的值"** 或是 "**前一個元素的最大值 + 自己的值"**

以下直接來看例子抓感覺

1. 先以 `[4, -1, -2, 1]`  舉例：

**第一個元素: 4**&#x20;

最大值為 4

子陣列為: \[4]

**第二個元素: -1**

最大值為 "**自己(-1)" or "前一個元素的最大值 (4) + 自己(-1)" = 3**

子陣列為: \[4, -1]

**第三個元素: -2**

最大值為 "**自己(-2)" or "前一個元素的最大值 (3) + 自己(-2)" = 1**

子陣列為: \[4, -1, -2]

**第四個元素: 1**

最大值為 "**自己(1)" or "前一個元素的最大值 (1) + 自己(1)" = 2**

子陣列為: \[4, -1, -2, 1]

\=> 最後解答要的最大值為第二個元素時的 3

2. 接著再以 `[-2, 1, -3, 4, -1]`  舉例來看：

**第一個元素: -2**&#x20;

最大值為 -2

子陣列為: \[-2]

**第二個元素: 1**

最大值為 "**自己(1)" or "前一個元素的最大值 (-2) + 自己(1)" = 1**

子陣列為: \[1]

**第三個元素: -3**

最大值為 "**自己(-3)" or "前一個元素的最大值 (1) + 自己(-3)" = -2**

子陣列為: \[1, -3]

**第四個元素: 4**

最大值為 "**自己(4)" or "前一個元素的最大值 (-2) + 自己(4)" = 4**

子陣列為: \[4]

**第五個元素: -1**

最大值為 "**自己(-1)" or "前一個元素的最大值 (4) + 自己(-1)" = 3**

子陣列為: \[4, -1]

\=> 最後解答要的最大值為第四個元素時的 4

觀察以上範例後，會發現核心公式只有兩條：

1. **到某個元素為止的最大值** = "**自己的值"** 或是 "**前一個元素的最大值 + 自己的值"**
2. **於每一輪中紀錄 子陣列加總最大值 = "原本的子陣列加總最大值" + "到某個元素為止的最大值"**

```javascript
var maxSubArray = function (nums) {
    // 最大總和數
    let max = nums[0];
    // 到某個元素為止的最大值
    let sum = nums[0];

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

    return max;
};
```

* `nums[i]` - **自己**
* `sum` - **到某個元素為止的最大值**

Runtime: 66 ms Beats 83.00% of users with JavaScript

Memory: 58.15 MB Beats 16.70% of users with JavaScript

**參考資料**

{% embed url="<https://ithelp.ithome.com.tw/articles/10273675>" %}

{% embed url="<https://hackmd.io/@Aquamay/B1nNuyyN5/https%3A%2F%2Fhackmd.io%2F%40Aquamay%2FBklfNQJEc#%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83>" %}
