[백준]10211번: Maximum Subarray

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

10211번: Maximum Subarray

---

🐥 브루트포스로 푸는 방법도 있지만, 문제를 보자마자 DP가 떠올라서 DP 풀어보았다.

 

 - 지금까지의 부분배열의 최대 합을 저장할 dp배열을 만든다.

 - dp[0] = arr[0]으로 초기화한다.

 

 - dp[1] ~ dp[n]까지 채운다

 

 - 매 인덱스마다 다음 두 가지 선택지가 생긴다.

 1) 현재까지의 최대 합(dp[i-1])에 현재값(arr[i])을 더하거나(즉, 부분배열의 마지막 원소로서 현재값을 추가하거나)

 2) 현재까지의 최대합을 버리고, 현재값(arr[i])을 시작으로 하는 새로운 부분배열을 만들거나

 - 일반항으로 다시 나타내보면
 1 ) dp[i] = dp[i-1] + arr[i]
 2 ) dp[i] = arr[i]

 - Maximum Subarray를 구하는 문제이므로 이 중에서 큰 값을 고르면 된당.

 

 - dp 배열 중 최대값이 정답이다.

 

🐥 Java 정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine());

        for (int t=0; t<T; t++){
        
        	// 입력받기
            int n = Integer.parseInt(reader.readLine());
            String[] strArr = reader.readLine().split(" ");

            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(strArr[i]);
            }

			// dp배열 생성 및 초기화
            int[] dp = new int[arr.length];
            dp[0] = arr[0];
            
            // dp배열 채우기
            for(int i=1; i<arr.length; i++){
                dp[i] = Math.max(arr[i]+dp[i-1], arr[i]);
            }
        
        	// 최대 합 구하기
            int answer = dp[0];
            for(int i=1; i<arr.length; i++){
                answer = Math.max(answer, dp[i]);
            }
			
            // 결과출력
            System.out.println(answer);

        }
    }
}

 

 

🐥 Kandane's Algorithm

 

 - 이 문제를 푸는 다른 알고리즘이 있다고 해서 이걸로도 코드를 짜봤다.

 - sum을 전부 구하고 나서 최댓값을 구하지 않고 그때그때 갱신해서 코드가 좀 더 간결해졌다

 - dp랑 거의 비슷한 것 같은데 조금 더 직관적인듯..?

 

코드

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

public class Main {
        public static void main(String[] args) throws IOException {
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            int T = Integer.parseInt(reader.readLine());

            for (int t=0; t<T; t++){
                int n = Integer.parseInt(reader.readLine());
                String[] strArr = reader.readLine().split(" ");

                int[] arr = new int[n];
                for (int i = 0; i < n; i++) {
                    arr[i] = Integer.parseInt(strArr[i]);
                }

                int answer = -Integer.MAX_VALUE;
                int currentSum = 0;
                for(int i : arr){
                  currentSum = Math.max(currentSum + i, i);
                  answer = Math.max(answer, currentSum);
                }

                System.out.println(answer);

            }
        }
  }

 

 

위 - Kandane's Algorithm

아래 - DP