PAT 연습 문제(갑 급)1007 Maximum Subsequence Sum(25 점)(동적 계획 을 간략하게 이해)(Java 구현)

PAT 연습 문제 1007 Maximum Subsequence Sum(25 점)

문제

제목

사고방식 분석

이해 동태 계획

동태 기획 사상(이런 문제 의 특징)

세 가지 모델

구 해 의 절차

동적 계획 알고리즘 을 실현 하 는 두 가지 사고

문제 코드 구현(주석 있 음)

문제
Given a sequence of K integers { N1, N2, …, NK}. A continuous subsequence is defined to be { N​i, Ni+1, …, Nj} where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.
Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.
Input Specification: Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.
Output Specification: For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.
Sample Input: 10 -10 1 2 3 4 -5 -23 3 7 -21
Sample Output: 10 1 4
제목

첫 번 째 줄 은 모두 몇 개의 요소 가 있 는 지,즉 두 번 째 줄 의 배열 의 길 이 를 K 로 기록 합 니 다.

두 번 째 줄 은 배열 요소 이다.

출력 첫 번 째 항목 은 하위 서열 의 최대 합 이 고 두 번 째 항목 은 하위 서열 의 왼쪽 끝 이 며 세 번 째 항목 은 하위 서열 의 오른쪽 끝 이다.

사고 분석.

은 서브 시퀀스 와 관련 된 문제 이기 때문에 동태 계획 이 적당 할 수 있 습 니 다.

은 두 가지 상황 이 있다.

첫 번 째:하나의 요소 만 양수 이 고 그것 이 우리 가 필요 로 하 는 결과 이다.

두 번 째:정상 적 인 구 해,구 하 는 하위 서열 에는 여러 개의 요소 가 포함 되 어 있다.

원 하 는 것 을 dp[i]로 기록 하면 상태 전이 방정식 은 dp[i]=max{list[i],dp[i-1]+list[i]}이 고 경 계 는 dp[0]=list[0]이다.

은 코드 실현 에 있어 매우 간단 하 다.많은 학우 들 이 평소에 사용 한 적 이 있 기 때문에 자세히 연구 한 적 이 없 을 것 이다.

C 와 C++의 실현 도 자바 와 같 고 문구 가 변 했 을 뿐 C 와 C++는 시간 적 으로 큰 장점 을 가진다.

동적 계획 이해

동태 계획 에서 흔히 볼 수 있 는 세 가지 문제 가 있 는데 저 는 문 제 를 푸 는 과정 에서 도 만난 적 이 있 습 니 다.

여기 서 인터넷 문서 와 자신의 이해 에 따라 조금 만 말 해 보 세 요.

동적 기획 사상(이런 문제 의 특징)

중첩 자 문제:예 를 들 어 한 회사 에서 이상 적 으로 회사 각 부서 에서 업무 가 가장 뛰어난 직원 을 알 게 되면 부서 의 책임자 도 부서 에서 가장 뛰어난 직원 을 알 아야 한다.이때 문제 가 겹 칠 수 있다.비록 하나의 문제 이지 만 두 사람 이 알 아야 한다.한 문제 의 답안 은 후속 적 인 구 해 에서 여러 차례 사 용 될 것 이다.

최 우수 서브 구조:이 문 제 는 최 우수 문제 로 이해 할 수 있 고 최 우수 문 제 는 최 우수 서브 구 조 를 선택 하 는 것 과 같다.

무 후 효성:이미 구 한 하위 문제 의 답안 은 후속 문제 의 구 해 로 인해 변 하지 않 을 것 이다.

세 가지 모형

선형 모델:피 보 나치 수열 의 전달 식,배열 의 증가 또는 체감 서브 시퀀스 문 제 를 참고 할 수 있 습 니 다.

구간 모델:문 제 를 자 문제 로 나 눈 다음 에 모든 자 문제 의 해답 을 구한다.

나무 모형:데이터 구조 에서 나무의 최 적 화 된 문제.

구 해 의 절차

구분 단계:문 제 를 구분 하고 구분 하 는 기준 은 문 제 를 해결 하 는 순서,즉 논리 적 순서 이다.분 단 된 서브 문 제 는 정렬 할 수 있어 야 한다.(내 가 보기에 어떤 문서 에는 문제 의 시간 이나 공간 특징 에 따라 문 제 를 몇 단계 로 나 누 었 다.)

상태 와 상태 변 수 를 확인 합 니 다.서브 문 제 를 전체 해결 절차 에서 의 상 태 를 확정 하고 비효 율 성 을 만족 시 켜 야 합 니 다.즉,미래 는 변 하지 않 습 니 다.

결정 을 확정 하고 상태 이전 방정식 을 작성 합 니 다.지난 단계 의 상태 와 결정 을 통 해 현재 단계 의 상 태 를 유도 하고 저 는 재 귀 와 유사 하 다 고 생각 합 니 다.(여기 서 피 보 나치 수열 을 참고 할 수 있 습 니 다)(우수한 블 로 거들 의 게시 물 에 따 르 면 결정 이 확정 되면 상태 이전 방정식 도 쓸 수 있 습 니 다.그러나 사실은 반대로 하 는 경우 가 많다.인접 한 두 단계 의 상태 간 의 관계 에 따라 결정 방법 과 상태 전이 방정식 을 확인한다.)

경계 조건 찾기:일반적으로 전이 상태 방정식 은 전달 식 이 므 로 중지 조건 이나 경 계 를 제정 해 야 한다.

동적 계획 알고리즘 을 실현 하 는 두 가지 사고

아래 에서 위로(아래 에서 위로):끊임없이 문 제 를 해결 하 는 서브 문 제 를 통 해 최종 적 으로 문 제 를 해결 하 는 해결 방안 은 교체 와 유사 하 다.

위 에서 아래로(위 에서 아래로):문 제 를 계속 분해 한 다음 에 하위 문 제 를 해결 하고 역방향 으로 답 을 저장 하면 문제 의 해결 방안 을 얻 을 수 있 으 며 재 귀 와 유사 하 다.

이라는 두 가지 방법 은 모두 문제 의 실제 상황 에 따라 최적화 할 수 있다.예 를 들 어 피 보 나치 수열 을 풀 때 매번 재 귀 결 과 를 얻어 재 귀 과정 을 가속 화 하 는 것 이지 매번 재 귀 할 때마다 똑 같은 연산 을 하 는 것 이 아니다.

제목 코드 구현(주석 있 음)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @Author:    
 * @QQ: 1579328766
 * @CreateTime: 2020-05-10-17-28
 * @Descirption: PAT   1007 Maximum Subsequence Sum (25 )
 */
public class Testseven {
    static int sum = 0;//       ，   for     ，   max  
    static int max = -1;//         ，              ，     0  ，    max -1，    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int K = Integer.parseInt(s);//K        ，         
        String[] strlist = br.readLine().split(" ");
        int[] list = new int[K];//      ，  K   
        int left = 0;//        
        int right = K-1;//        
        int temp = 0;//                ， max>0           temp   left

        //  for     int  
        for(int i = 0;i<K;i++)
        {
            list[i] = Integer.parseInt(strlist[i]);
        }

        //      ，            
        for(int i = 0;i<K;i++)
        {
            sum+=list[i];
            if(sum<0)
            {
                sum = 0;//         ，   sum  0     
                temp=i+1;
            }
            else if(sum>max)
            {
                max = sum;
                left = temp;
                right = i;
            }
        }
        if(max<0) max = 0;//  sum   max，   max<0  max=0
        System.out.println(max+" "+list[left]+" "+list[right]);
    }
}