[SW Expert Academy] 계산기 (D3)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AWxpQia60FgDFAWL&categoryId=AWxpQia60FgDFAWL&categoryType=CODE&problemTitle=&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=13

SW Expert Academy

 

bottom-up 방식으로 dp를 사용해서 풀었다.

 

import java.util.Scanner;

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

		for (int tc = 1; tc <= t; tc++) {

			int n = sc.nextInt();

			int dp[] = new int[n + 1];
			int a[] = new int[n+1];
			
			for(int i=1;i<n+1;i++) {
				a[i] = sc.nextInt();
			}
			
			for(int i=1;i<n+1;i++) {
				dp[i]=Math.max(a[i]+dp[i-1], a[i]*dp[i-1]);
			}
			
			System.out.println("#"+tc+" "+dp[n]);

		}

	}
}