혼란 스러웠습니다. "나누기와 정복 방식을 사용하여 n 개의 실수 (양수 또는 음수) 목록의 인접한 하위 목록에서 최대 합계를 찾는 효율적인 재귀 알고리즘을 작성합니다. 가치. "나누기와 정복을 사용한 최대 연속 합
나는 divide-and-conquer를 사용하지 않고 문제를 해결하는 방법을 알고 있지만 divide-and-conquer 방식을 사용하지는 않습니다.
도움에 감사드립니다!
목록 l을 두 개의 하위 목록 l1, l2로 나눕니다. l1_last, l2_first를 각각 l1의 마지막 요소 라하자. l2_first는 l리스트의 l1_last 바로 다음에 나옵니다.
s1a는 l1의 하위 목록 l1a에 l1_last가없고 l1b의 l1b가 l1_last를 포함하는 하위 목록 l1b의 최대 연속 합계가 최대 연속 합계 인 s1a를 찾습니다.
마찬가지로 l2에 대해 동일한 작업을 수행하고, s2a, l2a 및 s2b, l2b를 얻습니다. 여기서 l1_last는 l2_first로 바뀝니다. l의 서브리스트의 최대 연속 합은 s1a, s1b, s2a, s2b, s1b + s2b의 최대 값이며 대응하는 서브리스트 1a, l1b, l2a, l2b c (l1b, l2b)가 있습니다.
도움을 청합니다! 그러나 S1a와 S2a를 찾는 이유에 대해 혼란 스럽습니다. – Stephanie
최대 연속 합계가 이러한 하위 목록에서 발생할 수 있으므로 두 번째 "-1"에서 l = (1,1,1, -1, -1, -1) 분할을 고려하십시오. l1 = (1,1,1 , -1), l2 = (- 1, -1)이다. – gcc
알았습니다. 감사! – Stephanie