[066] 1912. 연속합

✨ 알고리즘 분류 : 다이나믹 프로그래

 

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

1912번: 연속합

 

---

 

 

🪡 문제에서 요구하는 조건 정리

 

- 연속합은 연속하는 수열들의 합이다

- 연속합 중 제일 큰 값을 출력

 

 

 

🧶 풀이과정 

 

이 문제는 간단하게 정리가 가능하다.

1 2 3 4 5 의 위치가 있고 현재 3의 위치에서 바라봤을 때 이전까지의 합 + 현재 위치의 수를 더한 것과 현재 위치의 수를 비교하고, 둘 중 높은 값을 누적해나가면 된다. 라고 써도 조금 헷갈릴 수 있으므로  내가 풀 때는 다음과 같이 정리했다.

 

 

그렇다면 dp[i-1] + nums[i] 와 nums[i] 중에 큰 값을 dp[i]에 담으면 되는 것!

+ 제일 큰 수의 경우에는 다시 반복문을 돌리거나 정렬을 수행하면 시간이 걸릴 것 같아 dp[i]가 확정된 후 기존 값과 현재 dp[i]의 값을 비교하여 높은 것을 저장하는 것으로 했다.

 

 

 

🏹 제출코드

 

package data_structure_part_01;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Q1912 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());


        int[] nums = new int[n+1];
        int[] dp = new int[n+1];

        for(int i = 1; i <= n ; i++){

            nums[i] = Integer.parseInt(st.nextToken());

        }

        int max = nums[1];
        
        for(int i = 1; i <= n ; i++){

            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);

            max = Math.max(max, dp[i]);
        }

        System.out.println(max);

        br.close();
    }
}