문제에서 주어진 조건에 따라 두가지 경우를 생각할 수 있다.
bottom-up방식을 이용하여
i번째 해당하는 수만 더하는 경우와 i-1번째 해당하는 수에 연이어 i번째 해당하는 수를 더하는 경우 중 어떤 것이 더 큰지를 나타낸다.
import java.util.Scanner;
public class ANS1912 {
static int N;
static int[] dp, A;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//N입력
N = sc.nextInt();
//수열 A, 배열 dp 선언 및 초기화
A = new int[N];
dp = new int[N];
for(int i = 0 ; i < N ;i++){
A[i] = sc.nextInt();
dp[i] = 0;
}
dp[0] = A[0];
int max = A[0];
for(int i = 1 ; i < N ; i++){
dp[i] = Math.max(dp[i-1] + A[i], A[i]);
max = Math.max(max,dp[i]);
}
System.out.println(max);
}
}
진짜 오랜만에 내 힘으로 풀었다..
다들 쉬운 문제라고 하지만, 나도 쉽다고 느낀것은 그만큼 동적계획법에 대해 이해하고 성장했다는 거 아닐까라는 긍정적인 생각을 해본다!!