boj)1912 - 연속합
2020. 9. 18. 01:47ㆍPS/boj
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class boj_1912{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int[] a;
static int[] dp;
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
/** 깔끔한 점화식 풀이
* for (int i = 1; i <= n; i++) {
* dp[i] = a[i];
* if (i == 0) continue;
* if (dp[i] < dp[i-1] + a[i]) {
* dp[i] = dp[i-1] + a[i];
* }
* }
*/
a = new int[n+1];
dp = new int[n+1];
int max = -1001;
for (int i = 1; i <= n; i++) {
a[i] = Integer.parseInt(st.nextToken());
if (a[i] > max) {
max = a[i];
}
}
for (int i = 1; i <= n; i++) {
if (dp[i-1] + a[i] > 0) {
dp[i] = dp[i-1] + a[i];
}
}
int ans = -1001;
for (int i = 1; i <= n; i++) {
if (dp[i] > ans) {
ans = dp[i];
}
}
// 음수일때
if (ans == 0) ans = max;
System.out.println(ans);
}
}
- 점화식을 깔끔하게 세울 생각이 안나서 음수 양수로 구분해서 풀었다.
- 그냥 초기에 dp[i] = a[i]로 주면 음양 구분이 필요없다.
- 풀이할때 정리
1. 머릿속에서 먼저 풀이방법 생각
2. 그 다음에 코드 작성
3. 예시 전부 돌리고 다시 한 번더 생각
'PS > boj' 카테고리의 다른 글
boj)2225 - 합분해 (0) | 2020.09.18 |
---|---|
boj)1699 - 제곱수 (0) | 2020.09.18 |
boj)14002 - 가장 긴 증가하는 부분 수열 4 (0) | 2020.09.18 |
boj)11053 - 가장 긴 증가하는 부분 수열 (0) | 2020.09.17 |
boj)2193 - 이친수 (0) | 2020.09.17 |