Java 알고리즘 최대 매출 구하기

설명
현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면
12 1511 20 2510 20 19 13 15
연속된 3일간의 최대 매출액은 11+20+25=56만원입니다.

입력
첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.

출력
첫 줄에 최대 매출액을 출력합니다.

아직 알고리즘에 익숙하지 않아서 모든 문제 풀이가 대체로 어렵지만 시간복잡도까지 고민해야할 때 더 어렵다.

public class Main { 

    public int solution(int n, int k, int[] arr) {
        int answer=0;
        int min = Integer.MIN_VALUE;
        for (int i=0; i<n-k; i++){
            answer = 0;
            for (int j=i; j<i+k; j++){
                answer += arr[j];
            }
            answer = Math.max(answer, min);
            min = answer;
        }
        return answer;
    }

}

가장 처음 풀었던 이중 for문 풀이법이다.
이중 for문으로 O(N^2)의 시간복잡도를 갖게 된다.

public class Main { 

    public int solution(int n, int k, int[] arr) {
        int answer;
        int sum = 0;
        for (int i=0; i<k; i++) sum += arr[i]; 		// 최초의 k개의 합 sum을 구한다.
        answer = sum;
        for (int i=k; i<n; i++){
            sum = sum+arr[i]-arr[i-k];			// 배열의 k번째 값을 sum과 더하고 처음값을 빼서 다음 k개의 합 sum을 구한다.
            answer = Math.max(answer, sum);		// 최댓값을 answer에 담는다.

        }
        return answer;
    }

}

단일 for문으로 O(N)의 시간복잡도로 알고리즘을 풀었더니 1385ms -> 755ms 당연한 결과로 거의 두배 가깝게 시간이 줄었다.

데이터가 많아지고 큰 프로젝트일수록 알고리즘의 중요성이 더 크게 느껴질텐데 더 잘해내야겠다..💡