[백준/JAVA] 1912번: 연속합

🔺 문제

1912번: 연속합

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
 
        String[] str = br.readLine().split(" ");
        int[] A = new int[100_001];
        for(int i = 0 ; i < n ; i++) {
            A[i + 1] = Integer.parseInt(str[i]);
        }
        
        long[] S = new long[100_001];
        S[1] = A[1];
 
        for(int i = 2 ; i <= n ; i++) {
            // 연속된 부분 수열의 합이 음수가 되는 경우에 대한 처리를 위해 다음과 같이 작성.
            if(S[i - 1] + A[i] < A[i]) {
                S[i] = A[i];
            } else {
                S[i] = A[i] + S[i - 1];
            }
        }
        
        long answer = -1000;
        for(int i = n ; i > 0 ; i--) {
            answer = Math.max(answer, S[i]);
        }
        System.out.println(answer);
    }
}

✅ 해결 아이디어
✔ DP (Bottom- Up)
- 2가지 경우의 수 생각하기
1) 이전부터 계속 연속된 값
2) 현재부터 연속된 값 의 경우
→ dp[i] = Math.max(dp[ i - 1 ] + A[ i ] , A[ i ] )

 

 

💥 유의사항

• 음수 양수 상관 없이 연속적으로 선택한 수의 합이 최댓값이 되는 수 찾기

 

 

 

---

🔺 다른 풀이들

- 최고의 설명 해설...ㅠㅠㅠ🤍🤍

[백준] 1912번 : 연속합 - JAVA [자바]

 

- 오.... 단순하고 이해할 수 있는 해설 (? 무슨 말이야 이게)

[BOJ] 백준 1912 - 연속합 (자바)

 

- 아 좋은 해설이다..

[BOJ] 백준 1912번 : 연속합 (JAVA)

 

 

- 점화식 세우는 과정 (복습용).

[백준 1912번] 연속합 (java)

---

💬 느낀 점

음수 경우의 수를 빼고 생각해버려서 틀렸었다..

그래도 나름 점화식 생각해냈다,,,

 

1회독	2회독	3회독	4회독	5회독
V	6.9	7.6	11.28

 

---

( + 6.9 2회독)

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int n = Integer.parseInt(br.readLine());
        int[] A = new int[n + 1];
        
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 1 ; i <= n ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        int[] S = new int[n + 1];
        S[1] = A[1];
        
        int max = A[1];
        for(int i = 2 ; i <= n ; i++) {
            S[i] = Math.max(S[i-1] + A[i], A[i]);
            
            max = Math.max(max, S[i]);
        }
 
        System.out.println(max);
    }
}

 

 

 

(+7.6 3회독)

까뭇다...

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        int[] A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        long[] dp = new long[N];
        dp[0] = A[0];
        
        long 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);
    }
}
 

 

 

(+11.28 4회독)

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        long[] dp = new long[N];
        dp[0] = arr[0];
        long max = dp[0];
        
        for(int i = 1 ; i < N ; i++) {
            dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
            max = Math.max(max, dp[i]);
        }
        
        System.out.println(max);
    }
}