https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
📌- 풀이
DP문제를 항상 어렵게 생각했는데 DP문제 치고는 생각보다 간단하게 풀었던 것 같음.
1. 값이 이렇게 들어온다고 생각할 때, 각각 값이 들어올때마다 최대값을 저장해주자라는 생각을 함
10부터 시작해서 10은 10 하나이므로 최댓값이 10이고,
-4의 경우에는 10에다가 -4를 더하는 값이 최대기 때문에 -4를 더해서
이런 식의로 전의 값과 비교해서 최댓값을 저장하면서 진행을 한다.
진행을 하다가 보면 이전 값은 -40인데 현재 값은 70이다 이럴 경우에는 이전 값을 더 해버리면 현재 배열의 값이 30이 되어버려서 최댓값을 구할 수 없게 되므로 (이전 값 + 현재 값)이 0보다 크지만 현재 값보다 작은 경우에는 현재 값으로 초기화를 해준다.
if(arr[i-1] + n < n){
arr[i] = n; // -> 여기에 해당하는 부분
}
마저 진행을 하면서 이전 배열의 값과 현재 자신의 값을 더한 값이 0보다 작을 때가 있는데 이럴때는 자기 자신을 넣어준다.
이렇게 하는 이유는 다음 값을 구할 때 이전 값이 필요하기 때문임
결과 적으로 새로운 배열을 사용하지 않고도 하나의 배열을 사용해서 결과 값이 나오게 되는데
아래의 배열이 얻게 된 배열이고 해당 배열에서 제일 큰 값을 출력하게 되면 얻을 수 있는 가장 큰 수가 된다.
🔥 - Java 코드
package DP.S2_1912_연속합;
import java.io.*;
import java.util.*;
public class Main {
public static int N;
public static Integer[] arr;
public static void main(String[] args) throws IOException {
//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new Integer[N];
st = new StringTokenizer(br.readLine());
arr[0] = Integer.parseInt(st.nextToken());
for(int i=1;i<N;i++){
int n = Integer.parseInt(st.nextToken());
if(arr[i-1] + n <=0){
arr[i] = n;
}else{
if(arr[i-1] + n < n){
arr[i] = n;
}else{
arr[i] = arr[i-1] + n;
}
}
}
Arrays.sort(arr,Collections.reverseOrder());
System.out.println(arr[0]);
}
}