Day 13 : Maximum Subarray

今天的题目是要我们在一个整数阵列中找到子阵列（subarray），也就是撷取阵列中相连的一部分，求出拥有最大的总和并且回传

而会让题目变得复杂的原因，是因为我们必须要考虑阵列中有包含负数。
如果是正整数阵列一定是整个加起来对吧？
假设今天我们有一个阵列为 [3, -2, 4]，
我们可以得到 3+ (-2) + 4 = 5 获得的总和比我们只拿３或４都还多，
但如果今天拿到的是[3, -5, 4]这时候我们就要单拿4会比较好。
因为-5後面的４不足以弥补-5对我们的伤害。

所以我们需要判断的应该就是：
负数後面出现的数到底有没有足以抵过他对我们的重击再决定要不要涵盖这个数对吧？

不过，光按照这个想法去解，我们还是很难想到要怎麽去实作。
这时候 Kadane's algorithm就派上用场了！
推荐阅读：Kadane’s Algorithm — (Dynamic Programming) — How and Why does it Work?
这一题要使用Dynamic programming来解，还记得DP的观念吗？
我们在Day03有提过，忘记了可以复习一下！

我们将从头开始去记录我们取到Array哪里(也就是index)，
每一次我们都会取目前可以得到的最大值，记录在目前的index。

也就是我们可以决定取前面那个数目前的总和加上当下的数，
或是放弃前面的总和，归零从现在当下的数开始累加。
MaxSumHere = max( MaxSumHere + 当下的number, 当下的number)

我们以这个原则，开始对阵列做检查

以上图为例:
一开始 MaxSumHere = -2
第一步骤我们比较现在的数 1 和 -2 + 1 = -1 取大的，也就是 1
代表我们目前的总和是１，又因为 1 > -2 所以目前的最大值会是１

第二步骤：比较 -3 和 -3 + 前面目前的最大和 1， 也就是 -2
但因为 -2 < 1，所以我们的目前最大总和不变

我们不段重复这个规则，直到这个阵列被拜访结束。
最後找到我们纪录中最大的数，就是题目要的答案。

Kadane's algorithm 很棒的地方在於：
我们不用一直重新循环检查，我们只需要拜访阵列一次，并且用一个变数来暂存我们目前存的最大总和即可。

此外，题目没有要我们回传一整个subarray，只是要最大的结果，所以我们只需要做在每一步骤时，另外比较当下的结果有没有比目前暂存的最大值还大，若有则取代，我们就不需要最後才去找出最大值。
时间复杂度为 O(N)，空间复杂度为 O(1)

最後来看实作吧!

var maxSubArray = function(nums) {
    let maxSumHere = nums[0];
	let maxSorFar = nums[0];
	for (let i = 1; i< nums.length; i++){
		const num = nums[i];
		maxSumHere = Math.max(num, maxSumHere + num);
		maxSorFar =  Math.max(maxSorFar, maxSumHere);
	}
	return maxSorFar;
};

明日题目预告：
凯撒密码的运用：Shifting Letters