# #53 Maximum Subarray (有圖)

[LeetCode](https://leetcode.com/problems/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.

out: 找找看相鄰的哪些加起來最大
```

```
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.
```

### Edge Case

* 只有一個就回傳那個值
* 會有負的喔

### 怎麼解

這題蠻值得思考的，我要鄰近數字加起來取 "最大值"，所以我可以自己跟前面比較取最大值

![](/files/-Lr2qvGGuk6gRCrC16y3)

![](/files/-Lr2r-5dVblbSOjEKBr-)

代表鄰近相加的總和，最後再取最大的，所以這個例子就是 6

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

};
console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))
```

### 學到什麼?

答案要什麼很重要，是一個值而已還是 Array，這題只要最大值所以我們不用去管是哪幾個相加起來只要著重在相加最大值是什麼就好了


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hannahpun.gitbook.io/leetcode-note/math/53-maximum-subarray.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.