题意概述

• 对于给定的长度为n的数组
• 找出连续子数组的最大和

方法一：暴力

思路与具体做法

两重循环，枚举子数组左右端点，这样找到所有子数组，累加出子数组和，并比较跟新最大连续子数组长度

class Solution {
public:
	int FindGreatestSumOfSubArray(vector<int> array) {
		int sum=INT_MIN; 
		for(int i=0;i<array.size();i++){//左边界 
			int sum2=0;
			for(int j=i;j<array.size();j++){//右边界 	
				sum2+=array[j];
				if(sum2>sum)sum=sum2;//更新最大连续子数组 
			} 
		} 
		return sum; 
	}
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(n^2\right)O(n^2)$O(n2)，用到了两层循环遍历子数组
• 空间复杂度：$O\left(1\right)O(1)$O(1)，仅用到了两个整形变量

方法二：动态规划

思路与具体做法

• dp[i]为以a[i]结尾的最大连续子列和
• dp[0]就是以a[i]结尾的且只有一个数可以直接赋值
• 进行状态转移，遍历dp数组，
• 对每个以自身结尾的最大连续子数组dp[i]，初始是它本身array[i]，即 $dp\left[i\right]=array\left[i\right]dp[i]=array[i]$dp[i]=array[i]
• 若它加上以前一个数组元素结尾的最大连续子数组能扩大，则直接加上前一元素结尾的最大子数组，得到 $dp\left[i\right]=max\left(array\right[i],dp[i-1]+array[i\left]\right)dp[i]=max(array[i],dp[i-1]+array[i])$dp[i]=max(array[i],dp[i−1]+array[i])

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
		vector<int>dp(array.size(),0);
		dp[0]=array[0];//边界
		for(int i=1;i<array.size();i++){ 
			dp[i]=max(array[i],dp[i-1]+array[i]);//若加前一状态子列和会使当前子列和减小则不加 
		} 
		int k=0;
		for(int i=1;i<array.size();i++){ //遍历以a[i]结尾的子序列的最大和
			if(dp[i]>dp[k])k=i;
		} 
		return dp[k];
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(n\right)O(n)$O(n)，循环遍历dp数组
• 空间复杂度：$O\left(n\right)O(n)$O(n)，仅用到了一个长度为n的dp数组