[D3] [Professional] 합 - 5642
성능 요약
메모리: 129,572 KB, 시간: 1,191 ms, 코드길이: 830 Bytes
제출 일자
2023-11-10 14:59
출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do
import java.util.Scanner;
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[] nums = new int[n+1];
for(int i = 0; i < n; i++){
nums[i] = sc.nextInt();
}
int[][] dp = new int[n][2];
dp[0][0] = dp[0][1] = nums[0];
for(int i = 1; i < n; i++){
int current = dp[i-1][0] + nums[i];
dp[i][1] = Math.max(dp[i-1][1],current);
if(current <= 0){
dp[i][0] = 0;
}else{
dp[i][0] = current;
}
}
System.out.println("#" + tc + " " + dp[n-1][1]);
}
}
}
디피를 좀 더 잘 활용하면 짧은 코드 사용 가능함
import java.util.Scanner;
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[] nums = new int[n];
int[] dp = new int[n];
for(int i = 0; i < n; i++){
nums[i] = sc.nextInt();
}
dp[0] = nums[0];
int max = dp[0];
for(int i = 1; i < n; i++){
dp[i] = Math.max(dp[i-1] + nums[i] , nums[i]);
max = Math.max(dp[i], max);
}
System.out.println("#" + tc + " " + max);
}
}
}
'알고리즘 - SWEA > D3' 카테고리의 다른 글
[SW expert Academy] SWEA 7732번 시간 개념 자바(Java) (0) | 2023.11.12 |
---|---|
[SW expert Academy] SWEA 9480번 민정이와 광직이의 알파벳 공부 자바(Java) (0) | 2023.11.12 |
[SW expert Academy] SWEA 3260번 두 수의 덧셈 자바(Java) (0) | 2023.11.10 |
[SW expert Academy] SWEA 3809번 화섭이의 정수 나열 자바(Java) (0) | 2023.11.10 |
[SW expert Academy] SWEA 3304번 최장 공통 부분 수열 자바(Java) (0) | 2023.11.10 |