한 줄 의 숫자 는 최대 하위 열 과 최 적 화 된 알고리즘 을 구한다.

문제: 주어진 K 개 정수 로 구 성 된 서열 {N 1, N 2,..., N K}, "연속 서브 열" 은 {N i, N i + 1,..., N j} 로 정의 되 며, 그 중 1 ≤ i ≤ j ≤ K 로 정의 된다.'최대 하위 열 과' 는 모든 연속 하위 열 요소 의 합 중 최대 자로 정의 된다.예 를 들 어 주어진 서열 {- 2, 11, - 4, 13, - 5, - 2} 의 연속 하위 열 {11, - 4, 13} 은 가장 큰 것 과 20 이 있 습 니 다.주어진 정수 서열 의 최대 하위 열 과 프로그램 을 작성 하 라 고 요구 합 니 다.
이 문 제 는 각종 서로 다른 알고리즘 이 각종 데이터 상황 에서 의 표현 을 테스트 하 는 데 목적 을 둔다.각 그룹의 테스트 데이터 특징 은 다음 과 같다.
데이터 1: 샘플 과 등가, 테스트 기본 정확성;데이터 2: 102 개의 무 작위 정수;데이터 3: 103 개의 무 작위 정수;데이터 4: 104 개의 무 작위 정수;데이터 5: 105 개 무 작위 정수;입력 형식: 첫 번 째 줄 을 입력 하여 정수 K (≤ 100000) 를 드 립 니 다.두 번 째 줄 은 K 개의 정 수 를 주 고 그 사이 에 빈 칸 으로 구분 합 니 다.
출력 형식: 한 줄 에 최대 하위 열 을 출력 합 니 다.시퀀스 의 모든 정수 가 마이너스 라면 0 을 출력 합 니 다.
온라인 처리 알고리즘: 이 문제 에 대해 어떻게 든 최적화 되 고 데 이 터 를 한 번 읽 어야 하기 때문에 시간 복잡 도 는 최소 O (n) 이 고 아래 에 소개 한 온라인 처리 알고리즘 은 바로 이와 같 습 니 다.
온라인 처리 라 는 이름 을 얻 은 이 유 는 이 알고리즘 이 이전에 데 이 터 를 뒤로 읽 고 특정한 숫자 를 읽 었 을 때 임시 최대 Sum 에 저 장 된 것 은 현재 읽 은 하위 문자열 의 최대 하위 열 과 같 기 때 문 입 니 다.
구체 적 인 코드 는 다음 과 같다.

#include
#define MAXSIZE 100000//     
int maxSum(int a[],int n);//         ，          
int main(){
	int n;//          
	int a[MAXSIZE];
	scanf("%d",&n);
	//           
	for(int i=0;isum){
			sum=thisSum;
		}
		//  thisSum  0，   0，              
		if(thisSum<0){
			thisSum=0;
		}
	} 
	return sum; 
}