algospot의 MAXSUM 문제:
scanning algorithm을 사용해야 함. scanning algorithm은 기본 concept는
--> '최대값 계산 시, 음수가 포함된다면 잘라내기'
라고 요약할 수 있겠다.
먼저 내가 작성한 source를 보자
package com.yongk.algospot.MAXSUM;
import java.util.Scanner;
public class MAXSUM {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = Integer.parseInt(sc.nextLine());
while(T-- > 0) {
int N = sc.nextInt();
sc.nextLine();
int[] input = new int[N];
String[] temp = sc.nextLine().split(" ");
for (int i = 0; i < N; i++) {
input[i] = Integer.parseInt(temp[i]);
}
System.out.println(getMaximumSetFast(input));
}
sc.close();
}
private static int getMaximumSetFast(int[] input) { //scanning algorithm
int max = 0;
int from = 0;
for (int i = 0; i < input.length; i++) {
from = Math.max(from + input[i], 0);
max = Math.max(max, from);
}
return max;
}
private static int getMaximumSetSlow(int[] input) { //처음 생각한 O(n^2)의 저속한 algorithm
int[] sum = new int[input.length];
sum[0] = input[0];
int max = 0;
for (int i = 1; i < input.length; i++) {
sum[i] = sum[i - 1] + input[i];
max = Math.max(max, sum[i]);
}
for (int i = 0; i < sum.length; i++) {
for (int j = i; j < sum.length; j++) {
max = Math.max(max, sum[j] - sum[i]);
}
}
return max;
}
}
- 처음 생각한 것이 getMaximumSetSlow()인데 나름 짱구를 굴려 미리 계산한 값으로 중복 계산을 줄이자는 생각이었지만 미개한 생각이었다.
- getMaximumSetFast()가 scanning algorithm. input[0]에서부터 더해가다가 그 값이 0보다 작아지면 당연히 거기까진 더할 필요가 없다. 왜냐하면 거기서부터 더하는건 0보다 크기 때문.
- 덕분에 scanning algorithm은 O(n)의 속도이다.
- 사람도 이렇게 생각하지 않을까?
덧1, python으로 같은 것을 구현하면
import sys
def getMaximumSetFast(input):
maxVal = 0
fromVal = 0
for i in input:
fromVal = max(fromVal + i, 0)
maxVal = max(fromVal, maxVal)
return maxVal
rl = lambda: sys.stdin.readline()
T = int(rl())
for i in range(T):
rl()
input = [int(j) for j in rl().split()]
print(getMaximumSetFast(input))
덧2. 그리고 java.util.Scanner()는 느리다..대따 느리다 ㅠㅠ 가급적이면 nextInt()보다는 nextLine()을 parseInt()할 것! 처음엔 다음과 같이 작성했었는데..참담한 속도였다. 적어도 5배 이상 느림.
while(T-- > 0) {
int N = sc.nextInt();
int[] input = new int[N];
for (int i = 0; i < N; i++) {
input[i] = sc.nextInt(); //slow!!!
}
System.out.println(getMaximumSetFast(input));
}
