53. Maximum Subarray

給定一個整數數列，找到其中加總最大的子數列

https://leetcode.com/problems/maximum-subarray/

範例
nums = [-2,1,-3,4,-1,2,1,-5,4]
當中加總最大的數列為[4,-1,2,1]，答案 = 6

思考的概念大致如下

先從短的數列 [ a , b , c , d ] 來看，我們要遍歷所有組合的話，隨元素逐筆加入，所有的數列組合如下

[a]

[a]
[a,b]
[b]

[a]
[a,b]
[b]
[a,b,c]
[b,c]
[c]

[a]
[a,b]
[b]
[a,b,c]
[b,c]
[c]
[a,b,c,d]
[b,c,d]
[c,d]
[d]

白字與紅字為所有子數列的組合，我們只要求出最大組合的即為解。

以這兩個區塊來討論，我們能觀察到兩件事

1. 紅字數列進入下一個組合時，會變為白字。
2. 紅字數列會和下一個整數組成新的數列。

秉持1. 這個規則，可知道「保留紅字曾出現過的最大值」即為解答。

而紅字的部分在加入新整數時又可以分成兩個情況

1. 加總的數列比較大
2. 新整數自己比較大

當出現第一種狀況時，我們將目前的值記下即可。出現第二種情況，可以知道前頭的數列是累贅，我們乾脆就捨去了，直接把最大值改成自己了，重新出發。

寫成程式碼會如下

	public int maxSubArray(int[] nums) {
		int answer = nums[0];
		int red = nums[0];

		for (int i = 1; i < nums.length; i++) {
			// 確認加總的數列，或是新整數哪個較大
			red = Math.max(red + nums[i], nums[i]);
			// 若出現最大值，則替換
			if (red > answer) {
				answer = red;
			}
		}
		return answer;
	}