7

前段时间我有一个面试问题，我从来没有得到解决方案。显然有一个“非常有效”的算法来解决它。

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

例子：

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

这里最好的子集是{4, 5, -1, 5}

除了蛮力方法，我想不出任何解决方案。什么是有效的方法？

4

5 回答 5

4

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

理论

如果当前子集总和大于零，它将有助于未来的子集总和，所以我们保留它。另一方面，如果当前子集总和为零或低于零，它将不会对未来的子集总和有所贡献。所以我们把它扔掉，重新开始一个新的子集总和。然后只需跟踪当前子集总和何时大于以前遇到的任何时间。

伪代码

list参数内是一个长度数组N。结果存储在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
    }

}
于 2012-08-29T05:54:12.973 回答
2

将列表转换为累积和列表，[1,-7,4,5,-1,5] to [1, -6, -2, -3, 2]。然后遍历累积和列表，保存迄今为止的最小值以及您看到的当前值与当前最小值之间的最大差值。从这里得到

于 2012-08-28T19:13:05.237 回答
1

You can answer this question from CLRS, which includes a tip:

Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem.

Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far.

Knowing a maximum sub array of A[1..j], extend the answer to find a maximum subarray ending at index j+1 by using the following observation:

a maximum sub array of A[1..j+1] is either a maximum sub array of A[1..j] or a sub array A[i..j+1], for some 1 <= i <= j + 1.

Determine a maximum sub array of the form A[i..j+1] in constant time based on knowing a maximum subarray ending at index j.

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)
于 2012-08-28T19:38:22.070 回答
1

这是以线性时间运行的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;
    }
}
于 2012-09-30T13:04:22.170 回答
1

太糟糕了 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);
    }
}

这是一些无耻的营销：我设法拼凑了一张幻灯片，说明这是如何工作的

于 2012-08-29T11:44:10.133 回答