
dp 문제라고는 하는데 약간 포인터 느낌이 나게 풀었다. memo를 쓰니까 이것도 dp의 일종인가??
이게 제일 효율적인 것 같은데 만약에 여기서 dp를 쓴다고 하면 dp[i] = Math.max(dp[i-1], dp[i-1] + input[i]);가 되려나..? (좀만 생각해봤는데 이거 안된다.)
푸는 방식은 이렇다.
1. sum과 max를 두고 그대로 input을 받는다.
2. 만약에 sum이 max를 넘으면 max에 할당한다.
시도는 다음과 같다.
1. input에서 -가 나오면 sum에 0을 할당한다. (실패)
input이 -가 나왔다고 해도 지금까지의 sum 값이 양수면 그대로 가져가는 것이 최대값이기 때문에 반례가 존재한다.
2. input값을 모두 sum에 넣고 만약 sum이 음수가 되면 그때 sum에 0을 할당한다. (성공)
package programers;
import java.util.Scanner;
public class BOJ1912_연속합 {
public static void main(String[] args) {
int sum = 0;
int max = Integer.MIN_VALUE;
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int i = 0; i < n; i++) {
int num = sc.nextInt();
sum += num;
max = Math.max(max, sum);
if(sum< 0) {
sum = 0;
}
}
System.out.println(max);
}
}