Найти максимальную подпоследовательность массива с индексами

Question

Я хотел бы найти максимальную подпоследовательность S(h,k) в массиве integer. У меня уже есть код (в 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 в ноль.

Answer 2

Благодаря SHREYAS Sarvothama и dasblinkenligh т для их ответов. Я нашел хорошее решение для этого кода, написанного Утсавом Чокши на сайте 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; 
     } 
}