온라인 에서 최대 하위 열 과 문제 구하 기 (복잡 도가 가장 낮 음)

01 - 복잡 도 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 - 211 - 4 13 - 5 - 2 출력 예시: 20 [해석] 현재 최대 하위 열과 음수 일 경우 현재 하위 열과 (0 으로 설정 하면) 를 버 립 니 다.하나의 음수 와 뒤의 수 를 더 하면 이것 과 더 작 을 수 있 기 때 문 입 니 다. 그렇지 않 으 면 하나의 수 를 더 해서 판단 합 니 다. 음수 라면 버 리 고 현재 최대 하위 열 과 크 면 현재 하위 열 과 를 업데이트 합 니 다.제목 분석: - 211 - 4 13 - 5 - 2 최대 하위 열과 첫 번 째 하위 열과 - 2 를 구하 고 현재 하위 열과 - 2 (0 이하, 버 림) 최대 하위 열과 0 두 번 째 하위 열과 11 을 구하 고 현재 하위 열과 11 의 최대 하위 열과 11 의 세 번 째 하위 열과 11 - 4 = 7 을 구하 고 현재 하위 열과 7 을 업데이트 하 며 최대 하위 열과 7 의 네 번 째 하위 열과 7 + 13 = 20 을 구하 고현재 하위 열 과 20 업데이트 최대 하위 열 과 20 다섯 번 째 하위 열 은 20 - 5 = 15, 15 < 20, 아무것도 하지 않 습 니 다. 하위 열 과 20 여섯 번 째 열 은 20 - 2 = 18, 18 < 20, 아무것도 하지 않 습 니 다. 하위 열 과 20 '온라인' 이라는 뜻 은 한 데 이 터 를 입력 할 때마다 즉시 처리 하고 어느 곳 에서 든 입력 을 중단 하 며 알고리즘 은 현재 의 해 를 정확하게 제시 할 수 있 습 니 다 [답].

import java.util.Scanner;//      ，    。        ，               ，       。
public class Main{
     
    public static void main(String[] args) {
     
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();//            
        int A[]=new int[N];//    
        for(int i=0;i<N;i++) {
     
            A[i]=sc.nextInt();//      
        }
        int max=MaximumSubsequenceSum(A,N);//          
        System.out.printf("%d",max);
    }
    public static int MaximumSubsequenceSum(int A[],int N)
    {
     
        int ThisSum=0,MaxSum=0;//     
        for(int i=0;i<N;i++){
     
            ThisSum+=A[i];
            if(ThisSum>MaxSum) {
     
                MaxSum=ThisSum;
            } else if(ThisSum<0) {
     
                ThisSum=0;
            }
        }
        return MaxSum;
    }
}