RSS Feed

합이 최대인 부분 수열 찾기

Problem 149

출제 일시 : 2020-08-01 00:04:08

아래 표에서 수평, 수직, 대각선 등 방향에 관계 없이 인접한 수를 더한 최댓값을 찾아보면 16 (= 8 + 7 + 1)입니다.

−2532
9−651
3273
−18−4  8

이제, 훨씬 더 큰 규모에서 다시 해 봅시다:

먼저, 아래의 "지연 피보나치 생성기(Lagged Fibonacci Generator)"를 이용하여 의사 난수 사백만 개를 생성합니다:

1 ≤ k ≤ 55 일 때, sk = [100003 − 200003k + 300007k3] (modulo 1000000) − 500000 입니다.
56 ≤ k ≤ 4000000 일 때, sk = [sk−24 + sk−55 + 1000000] (modulo 1000000) − 500000 입니다.

따라서, s10 = −393027이고 s100 = 86613입니다.

이제 2000×2000 표에 s 항을 배치하는데, 첫 2000 항을 첫 줄에, 다음 2000 항을 두번째 줄에, 이렇게 순차적으로 배치합니다.

끝으로, 어떤 방향이든 몇 개든 연속된 부분 수열의 최대 합을 구하세요.



로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.