思路

题目分析

1. 题目给出了一个整数数组
2. 要求我们返回其中子数组的和的最大值

• 方法一：暴力
  • 我们可以通过双重循环来对所有的子数组进行求和
  • 一重循环遍历起点，另一重循环遍历终点
  • 返回子数组求和的最大的那一个即可
• 方法二：动态规划
  • 我们规定dp[n]代表包括array[n]在内的子数组的和的最大值
  • 维护动态规划数组的操作即
    • 如果dp[n-1]>0，则dp[n] = dp[n-1] + array[n]，说明当前的元素要和前面累计的正数和加起来才是当前的子数组和最大
    • 否则dp[n] = array[n]
  • 最终返回dp数组中最大的一个即可

方法一：暴力

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int n = array.size();
        int mx = INT_MIN;
        for(int i = 0;i < n;i++){				// 外层循环遍历所有子数组起点
            int sum = array[i];
            for(int j = i+1; j < n; j++){		// 内层循环记录所有的子数组的和的值，并更新最大值
                mx = max(mx, sum);
                sum += array[j];
            }
            mx = max(mx, sum);
        }
        return mx;
    }
};

复杂度分析

• 时间复杂度：$O(N^2)O(N^2)$，双重循环的时间代价
• 空间复杂度：$O(1)O(1)$，未引入额外空间

方法二：动态规划

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int mx = array[0];
        vector<int> dp(array.size(),array[0]);
        for(int i = 1; i < array.size(); i++) {
            if(dp[i-1] > 0) dp[i] = dp[i-1] + array[i];		// 如果前面的子数组和累计为正数，则加到当前元素array[i]上才是包含当前元素的最大子数组和
            else dp[i] = array[i];							 // 否则不能用前面的和为负的部分
            mx = max(mx, dp[i]);							 // 保持更新最大值 
        }
        return mx;
    }
};

复杂度分析

• 时间复杂度：$O(N)O(N)$，只有一次循环
• 空间复杂度：$O(N)O(N)$，动态规划数组的空间消耗