[코드트리/INTERMEDIATE MID] 연속 부분 합의 최댓값 구하기 2 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• 그리디

현재까지의 원소들의 합 sum과 0 중 더 큰 값을 찾는다.

이 값과 현재 위치의 원소를 더해 원소들의 합을 갱신한다. 

원소들의 합과 최댓값을 비교해 더 큰 값으로 갱신한다.

 

 

 

🔺 코드

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

 

 

 

➕ 다른 풀이 방식

현재 연속 부분 수열 내 원소의 합이 0보다 작아진다면, 그 다음 원소에서부터 새로운 연속 부분 수열을 만든다.

import java.util.Scanner;
 
public class Main {
    public static final int MAX_N = 100000;
    
    public static int n;
    public static int[] arr = new int[MAX_N + 1];
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        n = sc.nextInt();
        for(int i = 1; i <= n; i++)
            arr[i] = sc.nextInt();
 
        int ans = Integer.MIN_VALUE;
        int sum = 0;
 
        for(int i = 1; i <= n; i++) {
            if(sum < 0)
                sum = arr[i];
            else
                sum += arr[i];
            
            ans = Math.max(ans, sum);
        }
        
        System.out.print(ans);
    }
}

 

---

💦 어려웠던 점

- 애초에 시작 원소가 음수이고, 죄다 음수만 입력받을 때는 어떻게 해야하지라는 생각을 했었다

 

🧐 새로 알게 된 내용

- 현재 연속 부분 수열 내 원소의 합이 0보다 작아지면, 새로운 연속 부분 수열을 만든다.

- 그렇지 않다면, 기존 연속 부분 수열에 현재 원소를 추가한다.

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[알고리즘]배열의 부분 최대합

[ 스터디 ] 그리디 + 구현 실전 모의 코딩 테스트