인덱스가있는 배열의 최대 서브 시퀀스 찾기

Question

정수 배열에서 최대 서브 시퀀스 S(h,k)을 찾고 싶습니다. 이미 최대 값을 찾을 수있는 코드 (Java)가 있지만 잘 작동하지만 두 인덱스를 얻으려면 어떻게해야합니까 h 및 k 다음 중 무엇입니까?

int []a = {-2, 1, -3, 4, -1, 2, 1, -5, 4 }; 
int max_so_far = 0, max_ending_here = 0; 
for(int i=0; i<a.length; i++) { 
    max_ending_here = Math.max(0, max_ending_here + a[i]); 
    max_so_far = Math.max(max_so_far, max_ending_here); 
} 
System.out.println("The maximal sum of subsequence is = "+max_so_far)"; 

Answer 1

당신은 max_so_far을 개선하는 마지막 인덱스를 저장하여 서브 자체를 얻고, 뒤에서 순서를 "탈피"할 수 있습니다

int []a = {-2, 1, -3, 4, -1, 2, 1, -5, 4 }; 
int max_so_far = 0, max_ending_here = 0, index_max = 0; 
for(int i=0; i<a.length; i++) { 
    max_ending_here = Math.max(0, max_ending_here + a[i]); 
    if (max_so_far < max_ending_here) { 
     max_so_far = max_ending_here; 
     index_max = i; 
    } 
} 
System.out.print("The maximal sum of subsequence is = "+max_so_far); 
int j = index_max; 
while (j >= 0 && max_so_far > 0) { 
    max_so_far -= a[j--]; 
} 
System.out.println(", from = "+(j+1)+" to "+index_max+", inclusive"); 

Demo.

참고 : 마커를 사용하여 뒤에서 풀다 보면 동적 프로그래밍 알고리즘의 공통된 주제가됩니다. 단순한 경우 index_max은 max_so_far이 0으로 실행되는 색인을 역방향으로 보는 특수 마커의 역할을합니다.

Answer 2

감사합니다. Shreyas Sarvothama 및 dasblinkenligh t 답에 감사드립니다. 나는이 코드가 Utsav Chokshi가 geeksforgeeks.org 웹 사이트에서 작성한 좋은 해결책을 발견했습니다.

솔루션은 다음과 같습니다

int []a = {-2, 1, -3, 4, -1, 2, 1, -5, 4 }; 
int max_so_far = a[0], max_ending_here = a[0]; 
int curStartIndex = 0; 
int maxStartIndex = 0; 
int maxEndIndex = 0; 

for(int i=1; i<a.length; i++) { 
     max_ending_here = Math.max(a[i], max_ending_here + a[i]); 
     if(max_ending_here > max_so_far){ 
      max_so_far = max_ending_here; 
      maxStartIndex = curStartIndex; 
      maxEndIndex = i; 
     } 
     if(max_ending_here < 0){ 
      curStartIndex = i+1; 
     } 
}