java - 查找具有索引的数组的最大子序列

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

感谢Shreyas Sarvothama和dasblinkenligh t 的回答。我在 geeksforgeeks.org 网站上找到了 Utsav Chokshi 编写的代码的一个很好的解决方案。

解决方案是：

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;
        }
}

Answer 2

您可以通过存储您改进的最后一个索引来获取子序列本身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");

演示。

注意：使用标记从背面拆开是动态编程算法中的常见主题。在您的简单案例index_max中，扮演一个特殊标记的角色，您可以从该标记向后查找max_so_far到零的索引。