문제

링크텍스트

풀이

이전에 풀었떤 가장 긴 증가수열 문제의 응용문제인데 DP로 안풀어집니다. 이유는 최대 10만번이 10만번 반복될 수 있는데 이 연산은 안됩니다. 그래서 저는 틀렸구용.

1. 1차 코드 - 시간 초과

for (int i = 0; i < n; i++) {
	dp[i] = arr[i];
    for (int j = i - 1; j > i - k && j >= 0; i--) {
        dp[i] += arr[i];
    }
    answer = Math.max(answer, dp[i]);
}

솔직히 단정하게 짜서 맘에는 들었으나 아마 이것보다 배열이 작은 경우에는 될것같습니당

그래서 이 문제를 보통은 투포인터로 푸는것 같습니다. 아무래도 투포인터로 푸는 것이 가장 보편적인 것 같기도하네요
제가 봤을땐 누적합으로 푸는 것이 더 깔끔하게 보여서 해당 코드를 정리해보겠습니다.

int[] arr = new int[n + 1]; // 누적합을 저장할 배열
for (int i = 0; i < n; i++) {
	// i배열까지의 누적합이 대한 배열을 정의
	arr[i] = arr[i - 1] + Integer.parseInt(st.nextToken());
}

// 마이너스 값들만 배열로 나올수 있기 때문에 가장 작은 값으로 초기화 해야합니다
int answer = Integer.MIN_VALUE;
for (int i =k;i <= n; i++) {
	// 현재까지의 누적합에서 
    // -k 만큼 뒤에 있는 누적합을 빼게 되면 k범위의 최대 값을 갱신할 수 있습니다
	answer = Math.min(answer, arr[i] - arr[i - k]);
}

근데 또 초등부 문제를 헤매고 있네요^^;; 정말 우리나라의 미래가 밝습니다.

전체 코드

전체 코드