SWEA[5642] - 합[D3]

링크

SWEA[5642]

문제설명

• 부분수열의 최대 합
• SWEA[3307] - 최장 증가 부분 수열[D3]랑 비슷

문제풀이

• 완전탐색 :O(N^2) -> DP :O(N)

문제코드

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution5642 {
    public static void main(String[] args) throws FileNotFoundException {
        //System.setIn(new FileInputStream("res/swea/5642.txt"));
        Scanner sc = new Scanner(System.in);

        int T=sc.nextInt();
        for (int test_case = 1; test_case <= T; test_case++) {
            int ans=0;
            int N = sc.nextInt();
            int[] arr = new int[N];
            for (int i = 0; i < N; i++) {
                arr[i]=sc.nextInt();
            }
            int[] max_arr = new int[N];
            int j=0;
            max_arr[0]=arr[0];
            for (int i = 1; i < N; i++) {
                max_arr[i]=Math.max(max_arr[i-1]+arr[i], arr[i]);
            }

            for (int i = 0; i < N; i++) {
                ans = Math.max(ans, max_arr[i]);
            }

            System.out.println("#"+test_case+" "+ans);
            /*
             * 초기화
             */
        }//end test_case
    }//end main
}

아쉬운점

• 댓글보고 O(N)접근하려함
  • O(N) 계산해보면 O(N^2)=10^10 이라 시간초과뜸

잘한점

• 1번에 함