# Maximum Subarray
###### tags: `leetcode`、`DP`

## 題目描述

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.

## 解法

#### 1. Kadane's Algorithm：
基於以下原則將陣列中的每個元素都當成結尾來思考，並且分成兩個部分計算這兩個部分的最大總和：陣列中的任一元素$A[i]$跟其他所有元素的排列組合，比如說$A[n]$會有以下的排列組合


把$A[n]$部分分成B部分，而剩餘部分當成A部分，接著在使用一些原則套用在這裡
1. A+B > B，所以納入A+B
2. A+B < B，所以只納入B

而如果要得到較大的總和，勢必得從A部分拿到一個最大總和的排列組合來搭配$A[n]$，而這樣會使A部分只需要當成另一個$A[n]$來思考，也就是找到$A[n-1]$和它的所有組合中最大總和的一組，接著又可以分成AB部分來求解，過程中不斷把問題切割成越來越小

$A[n]$ + $A_1$部分 -> $A[n-1]$ + $A_2$部分 -> ....

最後會得求出$A[1]$ + $A_n$部分來回朔至原本被切割的樣子，而這樣子的過程回朔至$A[n]$和$A_1$部分的問題，而最後回朔的答案並不一定會是最大總和，而是在某一元素$A[i]$和$A_i$部分中所得到的總和，只是我們不能夠知道，但是我們可以在求解過程中添加：

    globalmax = max(globalmax, localmax)

globalmax是最大總和，而localmax則是目前求解到的總和

## Reference

Kadane’s algorithm:
https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

https://en.wikipedia.org/wiki/Maximum_subarray_problem

https://medium.com/@rsinghal757/kadanes-algorithm-dynamic-programming-how-and-why-does-it-work-3fd8849ed73d