1007. Maximum Subsequence Sum(25)(java Edition)

Given a sequence of K integers { N1, N2, …, NK }. A continuous subsequence is defined to be { Ni, 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

아이디어:

동적 기획이란 다음 숫자를 현재 서열에 추가해야 하는지 아니면 다음 숫자를 새로운 서열로 간주해야 하는지를 판단하는 것이다. 첫 번째 숫자'10'이 첫 번째 서열 S1이라고 가정하면 두 번째 숫자'1'을 서열 S1에 추가해야 하는지 두 번째 숫자를 두 번째 서열 S2로 해야 하는지 판단하는 것이다. S1+'1'이 있으면'1'보다 작고그러면'1'은 두 번째 서열 S2의 첫 번째 수로서 세 번째 수인'2'를 판단한다. 분명히 S2+'2'는'2'보다 뒤에 있기 때문에'2'는 S2에 속한다. 그리고 맥스의 값을 계속 업데이트하면 답을 얻을 수 있다.왜 그런지 모르겠지만 처음에 쓴 테스트 포인트가 하나 있는데 인터넷에서 자바 코드를 많이 찾았어요. 그런데 ans의 값이 0으로 초기화되어서 순간 자신이 너무 멍청한 것 같았어요.

코드:

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int s = 0, e = 0;
        int ans1 = 0, ans2 = 0;
        int temp = 0, ans = -1000;
        int a1 = 0, a2 = 0;
        int dp = -1000;
        for(int i=0;iif(i == 0) {
                s = temp;
            }
            if(i == n-1) {
                e = temp;
            }
            if(dp + temp < temp) {
                dp = temp;
                a1 = a2 = temp;
            }
            else {
                dp += temp;
                a2 = temp;
            }
            if(dp > ans) {
                ans = dp;
                ans1 = a1;
                ans2 = a2;
            }
        }
        if(ans < 0) {
            System.out.println("0 " + s + " " + e);
        }
        else {
            System.out.println(ans + " " + ans1 + " " + ans2);
        }
    }
}