BOJ#13398 연속합2
* 문제
* 나의 코드
https://github.com/stack07142/BOJ/blob/master/BOJ%2313398_ContinuousSum2/src/Main.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* BOJ#13398 연속합2
* https://www.acmicpc.net/problem/13398
*/
public class Main {
static final int MIN = -100000000;
static int n;
static int[] arr = new int[100010];
static int[][] dp = new int[2][100010];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 2; i <= n + 1; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int maxValue = MIN;
for (int i = 2; i <= n + 1; i++) {
dp[0][i] = Math.max(dp[0][i - 1] + arr[i], arr[i]);
dp[1][i] = Math.max(dp[0][i - 2] + arr[i], dp[1][i - 1] + arr[i]);
maxValue = Math.max(dp[0][i], maxValue);
maxValue = Math.max(dp[1][i], maxValue);
}
/**
* dp[0][i] : 0번 건너뛴 i까지의 최대 연속합 = (i-1까지의 최대 연속합 + A[i])값과 A[i]값 중 큰 값
* dp[1][i] : 1번 건너뛴 i까지의 최대 연속합 = (i-1을 건너뛴 i까지의 최대 연속합)값과 (i-1을 안건너뛴 i까지의 최대 연속합)값 중 큰 값
*/
System.out.println(maxValue);
}
}
'Algorithm > DP' 카테고리의 다른 글
BOJ#11058 크리보드 (2) | 2017.04.05 |
---|---|
BOJ#12969 ABC (0) | 2017.04.05 |
BOJ#1520 내리막 길 (0) | 2017.03.31 |
BOJ#13460 째로탈출 2 (0) | 2017.03.31 |
BOJ#1670 정상 회담2 (0) | 2017.03.24 |