이 문제는 1차원 배열을 입력 받고, 단순히 가장 큰 값을 찾는 것이 아닌, 배열의 요소들중에서 가장 큰 값을 찾는 것이다.
일단 각 요소들의 합을 계산하기 위해서, 간단히 1차원 배열의 누적합을 구현한다.
그 이후, 서브 배열의 요소중 가장 큰 값을 구해야 하는데,
나는 위와 같이, 최대 길이에서, 1개씩 줄여가면서 max를 구하고 대입하는 방식으로 했다.
이번 문제는 배열의 길이가 1000이하라서 이런 알고리즘으로 구현이 됐지만,
내가 작성한 위 코드는 시간 복잡도가 O(T*N^2)이므로 효율적인 알고리즘이 아니다.
다이나믹 프로그래밍?을 공부하면 시간 복잡도를 효율적으로 코드를 짤수 있다는데, 나중에 공부하고 코드를 바꿔보는 식으로 해야겠다.
import java.io.*;
import java.util.StringTokenizer;
public class P10211 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int[] numArr = new int[N];
int[] prefixSum = new int[N+1];
for(int j = 0; st.hasMoreTokens(); j++) {
numArr[j] = Integer.parseInt(st.nextToken());
prefixSum[j+1] = prefixSum[j] + numArr[j];
}
int max = Integer.MIN_VALUE;
for(int j = 0; j < N+1; j++) {
for(int k = N; k > j; k--) {
max = Math.max(max,prefixSum[k]-prefixSum[j]);
}
}
sb.append(max +"\n");
}
System.out.println(sb);
}
}
'알고리즘 분류 > 누적합' 카테고리의 다른 글
2851 슈퍼 마리오 JAVA (0) | 2023.04.06 |
---|---|
2167 2차원 배열의 합 JAVA (0) | 2023.04.04 |
11660 구간 합 구하기 5 JAVA (0) | 2023.04.02 |
11441 합 구하기 JAVA (0) | 2023.04.01 |
23827 인간-컴퓨터 상호작용 (0) | 2023.04.01 |
이 문제는 1차원 배열을 입력 받고, 단순히 가장 큰 값을 찾는 것이 아닌, 배열의 요소들중에서 가장 큰 값을 찾는 것이다.
일단 각 요소들의 합을 계산하기 위해서, 간단히 1차원 배열의 누적합을 구현한다.
그 이후, 서브 배열의 요소중 가장 큰 값을 구해야 하는데,
나는 위와 같이, 최대 길이에서, 1개씩 줄여가면서 max를 구하고 대입하는 방식으로 했다.
이번 문제는 배열의 길이가 1000이하라서 이런 알고리즘으로 구현이 됐지만,
내가 작성한 위 코드는 시간 복잡도가 O(T*N^2)이므로 효율적인 알고리즘이 아니다.
다이나믹 프로그래밍?을 공부하면 시간 복잡도를 효율적으로 코드를 짤수 있다는데, 나중에 공부하고 코드를 바꿔보는 식으로 해야겠다.
import java.io.*;
import java.util.StringTokenizer;
public class P10211 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int[] numArr = new int[N];
int[] prefixSum = new int[N+1];
for(int j = 0; st.hasMoreTokens(); j++) {
numArr[j] = Integer.parseInt(st.nextToken());
prefixSum[j+1] = prefixSum[j] + numArr[j];
}
int max = Integer.MIN_VALUE;
for(int j = 0; j < N+1; j++) {
for(int k = N; k > j; k--) {
max = Math.max(max,prefixSum[k]-prefixSum[j]);
}
}
sb.append(max +"\n");
}
System.out.println(sb);
}
}
'알고리즘 분류 > 누적합' 카테고리의 다른 글
2851 슈퍼 마리오 JAVA (0) | 2023.04.06 |
---|---|
2167 2차원 배열의 합 JAVA (0) | 2023.04.04 |
11660 구간 합 구하기 5 JAVA (0) | 2023.04.02 |
11441 합 구하기 JAVA (0) | 2023.04.01 |
23827 인간-컴퓨터 상호작용 (0) | 2023.04.01 |