PTA7 - 1 최대 하위 열과 문제 (20 점)

PTA7 - 1 최대 하위 열과 문제 (20 점)
주어진 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 을 출력 합 니 다.
입력 예시:
6 -2 11 -4 13 -5 -2
출력 예시:
20
AC 코드:

#include
int main()
{
   int i,k;
   int sum,tmpsum;
   int n[100000];
   scanf("%d",&k);
   for(i=0;i<k;i++)
   {
      scanf("%d",&n[i]);
   }
   sum=0;
   tmpsum=0;
   for(i=0;i<K;i++)
   {
      tmpsum+=n[i];
      if(tmpsum>sum)
      {
         sum=tmpsum;
      }
      if(tmpsum<0)
      {
         tmpsum=0;
      }
   }
   printf("%d",sum);
   return 0;
}