최대 합계가있는 인접 서브 세트

def max_sublist(x): 
max1 = 0 
max2 = 0 
result = [] 
for i in x: 
    max2 = max(0, max2 + i) 
    max1 = max(max1, max2) 

print result

최대 합계를 가진 요소까지 요소를 추가하고 싶습니다. 결과에 어떤 요소 만 추가합니까?최대 합계가있는 인접 서브 세트

예 : 이 경우 x = [4, -1, 5, 6, -13, 2] 결과는 [4, -1, 5, 6]

출처

2014-02-11 user3295158

하위 세트가 항상 처음이나 목록에서 시작 되길 원하십니까, 아니면 중간에 어딘가에서 시작할 수 있습니까? –

알고리즘이 의도 한 바가 무엇인지는 분명하지 않지만 작동하지 않을 것이라고 확신합니다. 가장 인접한 부분 집합이 목록의 시작 부분에서 시작하지 않는 경우를 처리하는 것처럼 보이지 않습니다. – user2357112

http://stackoverflow.com/questions/15062844/maximum-sum-sublist#15063394를 참조하십시오. –

입니다. 이것은 최적화에서 일반적인 문제이며 maximum subarray problem입니다. 여기 Kadane's algorithm를 사용 O(n) 하나 개 가능한 동적 프로그래밍 솔루션이다 :

def max_val_contiguous_subsequence_idxs(seq): 
    i = thisSum = maxSum = 0 
    startIdx, endIdx = 0, -1 
    for j in xrange(len(seq)): 
     thisSum += seq[j] 
     if thisSum > maxSum: 
      maxSum = thisSum 
      startIdx = i 
      endIdx = j 
     elif thisSum < 0: 
      thisSum = 0 
      i = j + 1 
    return (maxSum, startIdx, endIdx)

(가) 상기 최대 합 시작 인덱스 서브 시퀀스의 끝 인덱스 단일 패스에서 튜플을 반환한다. 예를 들어, 문제의 샘플 입력을 사용하여 :

(당신이 목표로 한 솔루션과 매우 비슷) 위키 피 디아 페이지에 표시된 구현은 최대 금액을 제공하지만, 내 솔루션과 달리 것을

lst = [4, -1, 5, 6, -13, 2] 
maxSum, startIdx, endIdx = max_val_contiguous_subsequence_idxs(lst) 

maxSum 
=> 14 
lst[startIdx:endIdx+1] 
=> [4, -1, 5, 6]

공지 사항 그들은 배열에서 서브 시퀀스 인덱스를 찾는 방법을 알려주지 않습니다.

출처

2014-02-11 00:41:17

최대 합계가있는 인접 서브 세트

답변

관련 문제