题解 | #连续子数组的最大和#

描述
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).
输入：[1,-2,3,10,-4,7,2,-5]
输出：18
说明：输入的数组为{1,-2,3,10,—4,7,2,一5}，和最大的子数组为{3,10,一4,7,2}，因此输出为该子数组的和 18。

方法一：
小白解法，先固定一个最大值，再逐个从array[i]往回进行遍历相加，如果所得和大于max，对其进行更新。
int FindGreatestSumOfSubArray(vector<int> array) {
int max = array[0];
for(int i = 1; i < array.size(); i++)
{
if(array[i] > max)
{
max = array[i];
}
int temp = array[i];
int j = i-1;
while(j >= 0)
{
temp += array[j];
if(temp > max)
{
max = temp;
}
j--;
}
}
return max;
}
时间复杂度：O(n^2)
空间复杂度：O(1)
方法二：
从降低时间复杂度的角度出发进行考虑，上面小白做法，一个主要的缺陷是，反复计算之前计算过的数值，导致时间复杂度很高，因此采用dp[i]对数值进行保存，表示到i为止的最大和。
如果dp[i-1]+array[i]<array[i]，说明之前所有的和还不如array[i]大，因此dp[i]=array[i];
此外还需要一个max来保证获得最大值。
int FindGreatestSumOfSubArray(vector<int> array) {
vector<int>dp(array.size(),1);
dp[0] = array[0];
int max = dp[0];
for(int i = 1; i < array.size(); i++)
{
dp[i] = dp[i-1] + array[i];
if(dp[i] < array[i])
{
dp[i] = array[i];
}
if(dp[i] > max)
{
max = dp[i];
}
}
return max;
}
时间复杂度：O(n)
空间复杂度：O(n)</int></int></int>

方法三：
上述的时间复杂度降低了，但是空间复杂度很高，因此从降低空间复杂度的角度出发进行考虑。
上述空间复杂度主要是因为新建了一个数组用来存储i之前的最大和，想办法将这个最大和重新进行表示即可。
当前值：1 -2 3 10 -4 7 2 -5
之前和：0 1 -1 3 13 9 16 18
当前和：1 -1 3 13 9 16 18 13
最大和：1 1 3 13 13 16 18 18
当之前的和出现负值时，直接抛弃掉，tempSum 之前和，sum最大和，即tempSum = (tempSum>0)?tempSum+array[i]:array[i];
之后再对最大值进行确认，sum=sum > tempSum?sum:tempSum
int FindGreatestSumOfSubArray(vector<int> array) {
if(array.empty()) return 0;
int sum = array[0], tempSum = array[0];
for(int i = 1; i < array.size(); i++)
{
tempSum = (tempSum < 0) ? array[i] : tempSum + array[i];//之前的和的数值为负值的话直接扔掉
sum = (sum > tempSum) ? sum : tempSum;
}
return sum;
}</int>