杭电1003

最大子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package oj;

import java.util.Scanner;

public class Main_1003 {
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int t=scanner.nextInt();
		for(int i=0;i<t;i++){
			int n=scanner.nextInt();
			int max=-1001;
			int start=0;
			int end=0;
			int sum=0;
			int l=0;
			for(int j=0;j<n;j++){
				int a=scanner.nextInt();
				sum+=a;
				if (max<sum) {
					max=sum;
					start=l;
					end=j;
				}
				if (sum<0) {
					sum=0;
					l=j+1;
				}
			}
			System.out.println("Case "+(i+1)+":");
			System.out.println(max+" "+(start+1)+" "+(end+1));
			if (i!=t-1) {
				System.out.println();
			}
			
		}

	}

}

改成下面的。提交去掉1003

using namespace std;  
#include<string.h>  
using namespace std;  
int main()  
{  
    int t,i,j,sum,a,n,l,r,max,z;  
    cin>>t;  
    for(i=0;i<t;i++)  
    {  
        cin>>n;  
        for(z=l=0,r=0,sum=0,max=-1001,j=0;j<n;j++)  
        {  
            cin>>a;  
            sum+=a;  
            if(max<sum)  
            {  
                l=z;  
                r=j;  
                max=sum;  
            }  
            if(sum<0)  
            {  
                z=j+1;  
                sum=0;  
            }  
        }  
        cout<<"Case "<<i+1<<":\n"<<max<<" "<<l+1<<" "<<r+1<<endl;  
        if(i<t-1)  
            cout<<endl;  
    }  
}

http://blog.csdn.net/zhu_wei_jian/article/details/7393035
这是网络代码

我们假设
如果当an来临之前，我们知道了n－1里面最大的子序列是max，
想要超过max：
第一种理解：就得从an开始往an-1开始i 累加，每次累加记住一个临时变量sum，找到最大子序列，这个sum和max比较，哪个大，哪个就是n范围内最大子序列
第二种理解，从a0开始累加累加到aj如果sum为负数，就放弃前面，从aj＋1开始从新累加，一直到an
这样得到的sum和max比较，取大。就是n范围内最大子序列