思路一：暴力枚举

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;

int a[100]={0,-1,-3,3,5,-4,3,2,-2,3,6},n;
int s[100][100],smax=-99999;

int main(){
//	cin>>n;
	n=10;
//	for(int i=1;i<=n;i++)cin>>a[i];
	for(int l=1;l<=n;l++){
		for(int r=l;r<=n;r++){
			for(int i=l;i<=r;i++)s[l][r]+=a[i];
			if(s[l][r]>smax)smax = s[l][r];
		}
	}
	cout<<smax;
	return 0;
}

思路二：暴力优化

思路三：分治

思路四：动态规划递推

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;

int a[100]={0,-1,-3,3,5,-4,3,2,-2,3,6},n;
int d[100],smax=-99999;

int main(){
//	cin>>n;
	n=10;
//	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=n;i>=1;i--){
		if(d[i+1]<=0){
			d[i]=a[i];
		}else d[i]=a[i]+d[i+1];
	}
	for(int i=1;i<=n;i++){
		if(d[i]>smax)smax=d[i];
	}
	cout<<smax;
	return 0;
}

作业： 1、写实例代码和注释 2、输出最大数组和的每个数字

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;

int a[100]={0,-1,-3,3,5,-4,3,2,-2,3,6},n;
int d[100],r[100],smax=-99999,maxn;

int main(){
//	cin>>n;
	n=10;
//	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=n;i>=1;i--){
		if(d[i+1]<=0){
			d[i]=a[i];
			r[i]=i;
		}else{
			d[i]=a[i]+d[i+1];
			r[i]=r[i+1];
		} 
	}
	for(int i=1;i<=n;i++){
		if(d[i]>smax){
			smax=d[i];
			maxn=i;
		}
	}
	cout<<smax<<endl;
	for(int i=maxn;i<=r[maxn];i++){
		cout<<a[i]<<" ";
	}
	return 0;
}