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

方法一：动态规划

1、创建一个数组dp，记录不同位置结尾的子数组和的最大值，有两种情况，其一，当前的元素单独作为一个子数组；其二，与前面的元素组成子数组，所以可以得到如下的状态转移方程：

dp[i] = max(array[i], array[i] + dp[i - 1])；

2、数组dp中的最大值即为连续子数组的最大和。

时间复杂度：o(n)

空间复杂度：o(n)

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int>& array) {
        // 特殊情况处理
        if (array.size() == 1)
            return array[0];
        // 记录不同位置结尾的子数组和的最大值
        vector<int> dp(array.size(), 0);
        dp[0] = array[0];
        int max_sum = INT_MIN;
        for (int i = 1; i < array.size(); i++) {
            dp[i] = max(array[i], array[i] + dp[i - 1]);
            if (dp[i] > max_sum)
                max_sum = dp[i];
        }

        return max_sum;
    }
};

上述方法，可以进一步优化空间复杂度，使用一个临时的int值来存储上一个位置的最大子数组和即可。

时间复杂度：o(n)

空间复杂度：o(1)

#include <climits>
class Solution {
  public:
    int FindGreatestSumOfSubArray(vector<int>& array) {
        // 特殊情况处理
        if (array.size() == 1)
            return array[0];

        int max_sum = INT_MIN;
	  	// 存储上一个位置作为结尾的最大子数组和
        int temp = array[0];
        for (int i = 1; i < array.size(); i++) {
            temp = max(array[i], array[i] + temp);
            if (temp > max_sum)
                max_sum = temp;
        }

        return max_sum;
    }
};