항 저 우 전기 1231 1003 최대 연속 서브 시퀀스

최대 연속 서브 시퀀스
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 26280    Accepted Submission(s): 11816
Problem Description
K 개의 정수 서열{N1,N2,...,NK}을 지정 합 니 다.임의의 연속 하위 서열 은{Ni,Ni+1,...로 표시 할 수 있 습 니 다. 
Nj},그 중 1<=i<=j<=K.최대 연속 서브 시퀀스 는 모든 연속 서브 시퀀스 에서 요소 와 가장 큰 것 입 니 다. 
예 를 들 어 주어진 시퀀스{-2,11,-4,13,-5,-2}의 최대 연속 서브 시퀀스 는{11,-4,13}이 고 최대 와 
되다 
올해 데이터 구조 시험지 에 서 는 프로그램 작성 이 가장 큰 것 을 요구 합 니 다.지금 은 출력 이 필요 합 니 다. 
하위 시퀀스 의 첫 번 째 와 마지막 요소.
 
Input
테스트 입력 은 몇 가지 테스트 용례 를 포함 하고 모든 테스트 용례 는 2 줄 을 차지 하 며,첫 번 째 줄 은 정수 K(<10000)를 제시 하고,두 번 째 줄 은 K 개의 정 수 를 제시 하 며,중간 은 빈 칸 으로 구분한다.K 가 0 일 때 입력 이 끝나 면 이 용례 는 처리 되 지 않 습 니 다.
 
Output
모든 테스트 사례 에 대해 1 줄 에서 최대 와 최대 연속 서브 시퀀스 의 첫 번 째 와 마지막 원 을 출력 합 니 다. 
소,중간 에 빈 칸 으로 구분 합 니 다.최대 연속 서브 시퀀스 가 유일 하지 않 으 면 출력 번호 i 와 j 가 가장 작은 것(예 를 들 어 입력 사례 의 2,3 조)입 니 다.모든 K 개의 요소 가 음수 라면 최대 와 0 으로 정의 하고 전체 시퀀스 의 첫 번 째 요 소 를 출력 합 니 다. 
 
Sample Input

   
   
   
   

    
    
    
    6
-2 11 -4 13 -5 -2
10
-10 1 2 3 4 -5 -23 3 7 -21
6
5 -8 3 2 5 0
1
10
3
-1 -5 -2
3
-1 0 -2
0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    20 11 13
10 1 4
10 3 5
10 10 10
0 -1 -2
0 0 0


    
    
    
    
 
     
 
      Hint 
     
Hint 
    
    
    
    
     
Huge input, scanf is recommended.
   
   
   
   

 
총 사상:
최대 연속 하위 시퀀스 찾기:
처음부터 1 로 설정 하고 뒤의 모든 숫자 와 누적 합 니 다.
앞 과 더 불어 마이너스 가 되 지 않 는 다 면,
뒤에 어떤 숫자 가 이 서열 을 따라 가장 큰 것 을 얻 을 수 있 기 때문에 모든 정수 와 최대 여 부 를 보류 하고 판단 할 수 있다. 
더 하면 마이너스,
현재 와 0 을 리 셋 합 니 다.쉽게 말 하면 다시 계산 하 는 것 입 니 다.
작은 문제:
시작 점 및 종료 점 찾기
종료 점:이 문제 의 종료 점 이 상대 적 으로 큰 방향 은 찾기 쉽 지만 현재 몇 가지 요소 가 모두 마이너스,max=0 인 국면 이 존재 하기 때문에 첫 번 째 비 마이너스 점(또는 마지막 점)을 찾 아 종료 하려 고 합 니 다.
시작 점:나 는 중지 점 의 역방향 누적 으로 시작 점 을 얻 었 다. 

#include<iostream>
using namespace std;
int main()
{
	int n,a[10001],k,b[100001],max,i,j,sum,flag;
	//n：     a：       k：    b：              
	//max：    i：    j：   sum： j i    flag：               
	while(cin>>n)
	{
		if(n==0)
			break;
		for(k=0;k<n;k++)
			cin>>a[k];
		max=b[0]=0;
		i=j=0;
		flag=1;
		for(k=0;k<n;k++)
		{
			
			if(b[k-1]+a[k]>0)
			{
				b[k]=b[k-1]+a[k];
				if(b[k]>max)
				{
					max=b[k];
					j=k;
				}
			}
			else
			{
				b[k]=0;
				if(flag)//flag         
				{
					if(a[k]<0)
						j=k;
					else if(a[k]==0)//     
					{
						j=k;
						flag=0;
					}
				}
			}
		}
		sum=0;
		for(k=j;k>=0;k--)//        
		{
			sum+=a[k];
			if(sum==max&&a[k-1]!=0&&k-1>=0)
			{
				i=k;
				break;
			}
		}
		cout<<max<<" "<<a[i]<<" "<<a[j]<<endl;
	}
	return 0;
}

첨부:이 치 를 따 져 상술 한 경 계 를 찾 은 알고리즘 은 순 전 히 뇌 장애 이다.
다음은 기본적으로 같은 문제 입 니 다.
Max Sum
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 207182    Accepted Submission(s): 48449
Problem Description
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
 
Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
 
Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
 
Sample Input

   
   
   
   

    
    
    
    2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    Case 1:
14 1 4

Case 2:
7 1 6
   
   
   
   

 
코드 는 다음 과 같 습 니 다.(방법 은 프로그램 에 직접 적 습 니 다)

#include<iostream>
using namespace std;
int main()
{
    int n,m,k,i,t,a[100000],l,r,templ,tempr;
    cin>>m;
    for(t=0;t<m;t++)
    {
        cin>>n;
        
        for(k=0;k<n;k++)
        cin>>a[k];
        int max=a[0],sum=0;
        i=0;
        for(k=0;k<n;k++)
        {
            sum+=a[k];
            if(sum>=max)
            {
                max=sum;
                l=i;//    i    
                r=k;//       
            }
            if(sum<0)
            {
                sum=0;
                i=k+1;//      ，   
            }
            
        }

        cout<<"Case "<<t+1<<":"<<endl;
        cout<<max<<" "<<l+1<<" "<<r+1<<endl;
        if(t<m-1)cout<<endl;
    }
    return 0;
}

쉽 고 빠 르 죠?
사고,개선