합계가있는 목록의 하위 목록

Question

다음 두 속성 (최소 하나의 양수가 포함 된) 목록의 하위 목록을 찾으려고합니다. 1. 요소 합이 양수 입니다. 긍정적 인 합계를 가진 다른 모든 하위 목록의 최대 길이

나는 그 목록의 길이 만 흥미 롭습니다. Kadane의 알고리즘은 O (n) 시간에서 최대 합계를 갖는 하위 목록을 찾습니다. O (n)에서 같은 것을 할 수있는 알고리즘이 있습니까? 나는 해결책을 찾았지만 정말

그것이 n은 말할 시간

Answer 1

모든 숫자의 합을 계산 주셔서 감사합니다 .... 모든 하위 목록 계산하고 아주 아주 느린 과정이다. n> 0이면 전체 목록을 대답으로 반환하십시오. else 양쪽 끝에서 작은 요소를 잘라내어 합계가 양수가 될 때까지 빼십시오. 결과로 반환하십시오. O (n) 알고리즘입니다. 희망 하시겠습니까?

Answer 2

가능한 해결책은 여기에 있습니다. Counting sort을 사용하여 배열을 정렬 할 수 있습니다. 그 쳐다보고 양식 후 최대 요소는 합계를 확인 하고이 요소를 추가하는 경우 긍정 합계를 유지하지 않는 경우, 그것이 긍정적 인 경우 추가하고 증가 카운트를 앞두고 확인하십시오. 일부 입력에 버그가있을 수 있습니다. 모든 테스트 케이스에서 작동하지 않을 수 있습니다. 하지만 이것은 약간의 개선으로 원하는 결과를 얻을 수 있도록 도움이되는 아이디어 일뿐입니다. 하나의 순회 카운트 변수의 끝에있는 은 결과를 줄 것입니다. 예 :

array=[12,10,8,5,4,-2,-3,-20,-30] //considered already sorted now 
i=0 sum=12 count=1 
i=1 sum=22 count=2 
i=2 sum=30 count=3 
i=3 sum=35 count=4 
i=4 sum=39 count=5 
i=5 sum=37 count=6 
i=6 sum=34 count=7 
i=7 sum=14 count=8 
i=8 sum=14 count=8 //as now 30 cant be added 
so, here count=8 says maximum length sub array of 8 can give you positive sum. 

Answer 3

OK, 당신은 거의 이미 대답했다. 서브 시퀀스의 합보다 서브 시퀀스의 길이를 사용하도록 Kadane을 수정하십시오. 그것은 당신의 문제를 해결합니다. 다음은 위키 백과에서 Kadane의이다 : consequetive 요소, 나는 당신을 위해 작동합니다 Kadane의 너 한테에서 약간의 수정을 추측으로 답에서 유 하위 목록을 고려

int sequence(int numbers[])  
{ 
    // These variables can be added in to track the position of the subarray 
    size_t begin = 0; 
    size_t begin_temp = 0; 
    size_t len_temp = 0; 
    size_t end = 0; 

    // Find sequence by looping through 
    for(size_t i = 1; i < numbers.size(); i++) 
    { 
      // calculate max_ending_here 
      if(max_ending_here < 0) 
      { 
        max_ending_here = numbers[i]; 
        begin_temp = i; 
      } 
      else 
      { 
        max_ending_here += numbers[i]; 
        len_temp += (i - begin_temp); 
      } 

      // calculate max_so_far_len 
      if(len_temp >= max_so_far_len) 
      { 
        max_so_far_len = len_temp; 
        begin = begin_temp; 
        end = i; 
      } 
    } 
    return max_so_far_len ; 

}

Answer 4

입니다. max_length_till_now이라는 변수를 도입하십시오. 현재 값보다 큰 길이의 하위 목록을 찾을 때마다 업데이트하십시오.