在数组中随机整数。找到连续子集的最大和。

Question

我曾经遇到过一道面试题，但从未找到解决方法。显然有一种"非常有效"的算法可以解决它。

问题是：给定一个由随机正数和负数组成的数组，找到具有最大总和的连续子集。

例如：

[1, -7, 4, 5, -1, 5]

最佳子集是{4, 5, -1, 5}

我只能想到暴力方法，没有其他解决方案。那么高效的方法是什么？

- Earlz

---

请参阅：编程珠玑 - Paul R

好的，我会尽力进行翻译。下面是需要翻译的内容：提示：修改“Kadane算法”。 - noMAD

@noMAD- Kadane算法直接解决了这个问题吗？ - templatetypedef

@templatetypedef 不，它找到的是总和。在这里，我们想要的是索引。因此需要稍作修改。只是一种更加追求严谨的改变，没有其他什么特别之处 :) - av501

@templatetypedef：您可以比较实现Kadane算法的maxsum()和其修改版maxsumseq()，后者计算索引并从Greatest subsequential sum问题中返回子序列。 - jfs

嗨，我想知道除了效率之外，这个解决方案有什么问题： - user1479589

Answer 1

遍历列表，追踪到目前为止列表元素的局部和。如果局部和是迄今为止最高和，则记录下来。如果局部和达到或低于0，则将其重置并从下一个元素重新开始。

理论上，如果当前子集和大于零，则它将对未来的子集和有贡献，因此我们保留它。另一方面，如果当前子集和为零或小于零，则它不会对未来的子集和产生任何影响。所以我们放弃它，并从新的子集和重新开始。然后只需要跟踪当前子集和何时大于之前遇到的任何子集和即可。

伪代码中，输入参数是长度为N的数组list。结果存储在best_start和best_end中。

best_sum = -MAX
best_start = best_end = -1
local_start = local_sum = 0

for i from 0 to N-1 {

    local_sum = local_sum + list[i]

    if local_sum > best_sum {
        best_sum = local_sum
        best_start = local_start
        best_end = i
    }

    if local_sum <= 0 {
        local_sum = 0
        local_start = i+1
    }

}

- Jens Agby

---

良好的Kadane算法实现和清晰的解释。需要注意的是，如果数组中所有整数都是负数，并且您必须选择数组的某个实际子集（而不是空集{}），则必须添加一个最后的检查来获取最接近零的负数。例如，如果给定[-3，-7，-1，-2]，答案应该是{-1}。 - mVChr

我的伪代码实际上已经处理了这个问题，因为我将best_sum初始化为最大的负整数（-MAX）（我同意我本可以解释得更好）。 - Jens Agby

哇，真是太棒了！干得好！ - mVChr

Answer 2

将列表转换为累加和列表，将[1,-7,4,5,-1,5]转换为[1, -6, -2, -3, 2]。然后遍历累加和列表，保存迄今为止最小值和当前值与当前最小值的最大差异。

来源：这里。

- noMAD

Answer 3

这是一个在线性时间内运行的Java类。

public class MaxSumOfContinousSubset {

    public static void main(String[] args) {
        System.out.println(maxSum(1, -7, 4, 5, -1, 5));
    }

    private static int maxSum (int... nums) {
        int maxsofar = 0;
        int maxhere = 0;
        for (int i = 0; i < nums.length; i++) {
            maxhere =  Math.max(maxhere + nums[i], 0);
            maxsofar = Math.max(maxhere, maxsofar);
        }
        return maxsofar;
    }
}

- craftsmannadeem

---

解释通常比直接实现更有用。 - adrianton3

Answer 4

您可以从CLRS中找到答案，其中包含一个提示：

使用以下思路开发非递归的线性时间算法来解决最大子数组问题。

从数组的左端开始，向右移动，跟踪到目前为止看到的最大子数组。

已知A [1..j]的最大子数组，通过使用以下观察结果将答案扩展到找到以索引j + 1结尾的最大子数组：

A [1..j + 1]的最大子数组要么是A [1..j]的最大子数组，要么是A [i..j + 1]的子数组，其中1 <= i <= j + 1。

基于已知以索引j结尾的最大子数组，以常数时间确定形式为A [i..j + 1]的最大子数组。

max-sum = A[1]
current-sum = A[1]
left = right = 1
current-left = current-right = 1
for j = 2 to n
    if A[j] > current-sum + A[j]
        current-sum = A[j]
        current-left = current-right = j
    else
        current-sum += A[j]
        current-right = j
    if current-sum > max-sum
        max-sum = current-sum
        left = current-left
        right = current-right
return (max-sum, left, right)

- Avi Cohen

Answer 5

很遗憾Java没有元组返回类型。因此，必须在方法中打印索引和总和。

public class Kadane {

    public static void main(String[] args) {
        int[] intArr = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
        findMaxSubArray(intArr);
    }

    public static void findMaxSubArray(int[] inputArray){

        int maxStartIndex=0;
        int maxEndIndex=0;
        int maxSum = Integer.MIN_VALUE; 

        int sum= 0;

        for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) {
            int eachArrayItem = inputArray[currentIndex];

            sum+=eachArrayItem;

            if( eachArrayItem > sum){
                maxStartIndex = currentIndex;    
                sum = eachArrayItem;      
            }
            if(sum>maxSum){
                maxSum = sum;
                maxEndIndex = currentIndex;
            }
        }

        System.out.println("Max sum         : "+maxSum);
        System.out.println("Max start index : "+maxStartIndex);
        System.out.println("Max end index   : "+maxEndIndex);
    }
}

这里有一些不要脸的市场营销：我成功制作出了一个slide，介绍了这个如何运作。

- Arun Manivannan