[Algorithm] 연속합

이번 문제는 연속 된 수의 합 중 가장 큰 합을 구하는 문제다.

문제에서 드러나듯이 DP를 활용해 풀 수 있는 문제라 생각하였다.

처음 나의 아이디어는 다음과 같았다.

"C[N]에 1 ~ N까지의 연속합 중 가장 큰 연속 합을 저장하자"

그렇기 위해선 한 가지 조건만이 필요했다.

"V[N] + C[N-1] > 0 이면 C[N] = V[N] + C[N-1] 이고 

V[N] + C[N-1] < 0 이면 C[N] = C[N-1]이다 !"

처음에 이렇게 생각하고 접근을 하다 보니 연속성에 대한 문제가 생겼다.

만약 10 -4 3 1 5 6 -35 12 21 -1 같은 경우 -35에서 내 해결 방법 같은 경우는 해당 하는 

값이 들어가지 않고 21이 들어가게 된다. 그 다음 V[N] = 12가 되게 되는 경우 

C[N] = 12 +21 이 되고 이는 연속된 수가 아니기 때문에 모순이 생기게 된다.

그렇기 때문에 나는 문제를 다시 생각해 보기로 하였다.

처음의 아이디어를 버렸고 , 한가지 확실해 진 것이 있었다. sum변수를 두어 

V[N] + sum < 0 이게 되면 sum = 0 을 하여 새롭게 초기화를 하고 max변수와 sum을 

비교하여 가장 큰 값을 저장 해 놓는 것이다.

아래와 같이 해결하였다. 끝 !!

소스코드:

package algorithm;

import java.util.Scanner;

public class a_1912 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int max = -1001;
int sum = 0;
for(int i =0;i<N;i++){
sum += sc.nextInt();
if(sum>max)max=sum;
if(sum<0)sum=0; //sum초기화
}
System.out.println(max);
}

}