题意：求MCS(最大连续子序列和)及两个端点

分析：第一种办法：dp[i] = max (dp[i-1] + a[i], a[i]) 可以不开数组，用一个sum表示前i个数字的MCS，其实是一样的。。。类似DP的做法有个名字叫。

　　　第二种办法：一个前缀记录前i个数字的和，那么ans = sum - mn; mn表示前j个和且和最小

　　　两种办法都是O (n) 1003就这么难？？ 推荐学习资料：

 

收获：MCS问题的两种o (n) 的算法，且还有递归的解法 O (nlogn)

 

代码1：

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int N = 1e6 + 10;const int INF = 0x3f3f3f3f;int a[N];//O (n)void MCS(int n)	{	int l = 0, ll = 0, rr = 0;	int sum = -INF, mx = -INF;	for (int i=1; i<=n; ++i)	{		if (sum + a[i] < a[i])	{			sum = a[i];	l = i;		}		else	sum += a[i];		if (sum > mx)	{			mx = sum;	ll = l, rr = i;		}	}	printf ("%d %d %d\n", mx, ll, rr);}int main(void)	{	int T, cas = 0;	scanf ("%d", &T);	while (T--)	{		int n;	scanf ("%d", &n);		for (int i=1; i<=n; ++i)	scanf ("%d", &a[i]);		printf ("Case %d:\n", ++cas);		MCS (n);		if (T)	puts ("");	}	return 0;}
       
      
     

 

代码2：

//O (n) //anothervoid MCS(int n)	{	int l = 0, ll = 0, rr = 0;	int sum = 0, mx = -INF, mn = 0;	for (int i=1; i<=n; ++i)	{		sum += a[i];		if (sum - mn > mx)	{			mx = sum - mn;	ll = l;	rr = i;		}		if (sum < mn)	{			mn = sum;	l = i;		}	}	printf ("%d %d %d\n", mx, ll + 1, rr);}