[알고리즘][DP][1912] 연속합

[알고리즘][DP][1912] 연속합

https://www.acmicpc.net/problem/1912

[풀이]

• n = 입력받는 수의 갯수
• numbers[i] = 입력받는 수
• 이 때, numbers[i] 는 두 가지 경우를 고려해야 한다.
1. numbers[i] 가 result[i-1]과 합했을 때
2. numbers[i] 가 새로운 연속합을 시작했을 때
3. 이 두 가지 경우를 고려해 최대값을 result배열에 넣어준다.
• result[i] = max( result[i-1]+numbers[i] , numbers[i] )
• result[i] 배열에서 가장 큰 수를 ans에 담아준다.

[코드]

package algorithm_basic;
 
import java.util.Scanner;
 
 
public class q_1912_2 {
    
    public static void main(String[] args)   {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] numbers = new int[n];
        for (int i=0;i<n;i++) {
            numbers[i] = scan.nextInt();
        }
        int[] result = new int[n];
        for(int i=0;i<n;i++) {
            result[i] = numbers[i];
            if(i==0) continue;
            if(result[i-1] + numbers[i]>result[i]) {
                result[i] = result[i-1] + numbers[i];
            }
        }
        int ans=result[0];
        for(int i=0;i<n;i++) {
            if(result[i]>ans)
                ans=result[i];
        }
        
        System.out.println(ans);
    }
 
 
}