홀수 길이의 연속 부분 배열의 합 중 가장 큰 값을 구하는 방법

19355번: A Really Odd Sequence (acmicpc.net) 주어진 배열에서 길이가 홀수인 연속 부분 배열의 원소 합 중 가장 큰 값을 구하는 문제 https://deepdata.tistory.com/390 다이나믹 프로그래밍 - Kadane algorithm1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거deepdata.tistory.com 카데인 알고리즘의 연장선상이긴 한데 문제는 홀수 길이여야한다는 것... 카데인 알고리즘은 배열의 길이를 모른다.. 길이 정보를 담자니...

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2024. 8. 5.
• textsms

다이나믹 프로그래밍 - Kadane algorithm

1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net 주어진 n개의 임의의 수열에서 1개 이상의 연속된 부분 수열을 선택할 때, 가장 큰 합을 출력  2. 나의 풀이 단순한 규칙, 점화식으로는 풀기 어렵다 메모리, 시간제한 문제로 $O(N^2)$으로도 통과하기 어렵다 처음에 i번째부터 j번째까지 수열의 합을 dp[i][j]에 저장해서 테이블을 완성하려고 했는데 n의 최대가 100000이라 10만*10만 만들자 마자 메모리 초과 from sys impor..

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2022. 9. 4.
• textsms