[SWEA] 3819. 최대 부분 배열

[SWEA] 3819. 최대 부분 배열

제출일 : 2019-12-09

문제 풀이 시간 : 1H 45M

난이도 : ★★★☆

Problem

link : https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxo6c6AVkDFAW4#

길이 $N$ 짜리 배열$A[1…N]$이 주어질 때,

부분 배열의 합 $\sum_{k=i}^j A[k]$의 최댓값을 구하는 프로그램을 작성하라. $(1 ≤ i ≤ j ≤ N)$

input

첫 줄에 테스트케이스의 개수 $T$가 주어진다. $(T ≤ 20)$

각 테스트케이스마다 첫 줄에 $N(N ≤ 200,000)$이 주어지고, 다음 $N$ 줄에 걸쳐 각 줄마다 차례대로 $A[i]$가 주어진다.$(|A[i]| ≤ 1,000)$

Output

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 러시아 국기 같은 깃발을 만들기 위해서 새로 칠해야 하는 칸의 개수의 최솟값을 구하여 T 줄에 걸쳐서 출력한다.

Example

input

2
1
3
5
1
3
-5
3
6

output

#1 3
#2 9

Solution & Inpression

길이 N의 최대값이 200,000이기때문에 모든 경우의 수를 구해 최적해를 구하는 방법으론 풀수 없는 문제로
$$
\sum_{k=i}^j A[k]= \sum_{k=1}^j A[k]-\sum_{k=1}^i A[k]
$$
i부터 j까지의 부분 배열의 합은 1부터 j까지의 부분배열의 합에서 1부터 i까지의 부분배열의 합을 뺀것과 같다.

따라서, 입력을 받으며 누적합(1부터 j까지의 부분배열의 합)을 갖는 배열 sum과 누적합의 최솟값(1부터 i까지의 부분 배열의 합)을 갖는 배열 min을 이용하여 문제를 해결하였다.

Code 1

언어 : JAVA

import java.util.Scanner;

class Solution {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T;
        T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            int N = sc.nextInt();
            int[] input = new int[N + 1];
            int[] sum = new int[N + 1];
            int[] min = new int[N + 1];

            for (int i = 1; i <= N; i++) {
                input[i] = sc.nextInt();
                sum[i] = sum[i - 1] + input[i];
                min[i] = sum[i] > min[i - 1] ? min[i - 1] : sum[i];
            }

            int max = sum[1];
            for (int i = 2; i <= N; i++) {
                if (max < sum[i] - min[i - 1])
                    max = sum[i] - min[i - 1];
            }
            System.out.println("#" + tc + " " + max);
        } // end of TC
        sc.close();
    }// end of main
}

Code 2

언어 : JAVA

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            int N = sc.nextInt();
            int[] A = new int[N];

            A[0] = sc.nextInt();

            int max = A[0];
            for (int i = 1; i < N; i++) {
                int num = sc.nextInt();
                A[i] = num;
                if (A[i - 1] + A[i] > A[i]) {
                    A[i] = A[i - 1] + A[i];
                }
                if (max < A[i]) {
                    max = A[i];
                }
            }

            System.out.println("#" + tc + " " + max);
        }
    }
}