找出实数列表中的最大区间和

Question

这是一位同事询问编程职位的面试问题。我认为这对于观察受访者的思考非常有用。我很想得到 SO 社区的看法。

给定一个长度为 N 的实数列表，例如 [a_1, a_2, ..., a_N]，找到存在索引 1 <= i 的最大值 M 的复杂度是多少<= j <= N 使得

a_i + a_{i+1} + ... + a_j = M？

如果这是一个经典的计算机科学问题，我很抱歉。

Answer 1

Kadane 算法的复杂度仅为 O(n)：

算法会跟踪(maxSum, maxStartIndex, maxEndIndex)中的暂定最大子序列。它在 currentMaxSum 中累积部分和，并在该部分和大于 maxSum 时更新最佳范围。

Answer 2

这是O(N)：

int sum = 0;
int M = 0;  // This is the output
foreach (int n in input)  {
  sum += n;
  if (sum > M)
      M = sum;

  if (sum < 0)
    sum = 0;
}

这个想法是保留自上次重置以来遇到的所有整数的总和。当总和低于零时，即发生重置，即当前间隔中有太多负数而无法使其成为最佳间隔。

Answer 3

这是一个众所周知的经典问题，在任何算法课程中都是一个令人大开眼界的问题。很难找到更好/更简单的启动器。
您可以找到 n*3-、n*2-、nlogn- 甚至简单的 n 算法。

我在 John Bentley 1986 年的《Programming Pearls》中找到了讨论/解决的问题 -
多年来，我们在 NTNU/Trondheim 的算法课程中一直使用它作为入门课程。
大约 20 年前，我第一次在大约 250 名学生的考试中使用它，其中只有 1 名学生发现了所有 4 个解决方案，见上文。他，Bjørn Olstad，成为特隆赫姆 NTNU 的“有史以来最年轻的教授”，除了领导奥斯陆的 MSFT 搜索部门外，现在仍然保持着这一地位。
Bjørn 还接受了挑战，寻找算法的良好实际应用。你看到一些吗？

• 阿恩·哈拉斯

Answer 4

试试这个代码..对于数组中至少一个+ve数字来说它可以正常工作..O(n)只使用一个for循环..

public static void main(String[] args) {
    int length ;
    int a[]={-12, 14, 0, -4, 61, -39};  
    length=a.length;

    int absoluteMax=0, localMax=0, startIndex=0, lastIndex=0, tempStartIndex=0;
    for (int index=0;index<length;index++) {
        localMax= localMax + a[index];
        if(localMax < 0){ localMax=0; tempStartIndex = index + 1;}
        if(absoluteMax < localMax) {
            absoluteMax = localMax; 
            lastIndex =index; 
            startIndex=tempStartIndex;
        }
    }

    System.out.println("startIndex  "+startIndex+"  lastIndex "+ lastIndex);    
    while (startIndex <= lastIndex) {
        System.out.print(" "+a[startIndex++]);
    }
}

Answer 5

这可能是错误的，因为它简单得令人怀疑。

1. 开始对从 0 到 n 的所有元素求和，并确定滚动总和最高的索引。这将是您的间隔的上限。
2. 向后做同样的事情以获得你的下边界。 （如果从上边界开始就足够了。）

这看起来像 O(n)。

Answer 6

我介入这个古老的话题是为了详细解释 Kadane 算法的工作原理。该算法是在我目前正在上的一堂课上介绍的，但只有一个模糊的解释。这是该算法在 Haskell 中的实现：

maxCont l = maxCont' 0 0 l

maxCont' maxSum _ [] = maxSum
maxCont' maxSum thisSum (x:xs)
  | newSum > maxSum = maxCont' newSum newSum xs
  | newSum < 0      = maxCont' maxSum 0 xs
  | otherwise       = maxCont' maxSum newsum xs
  where
    newSum = thisSum + x

现在，由于我们只是想了解该算法，所以让我们撤消命名 newSum 的小优化：

maxCont l = maxCont' 0 0 l

maxCont' maxSum _ [] = maxSum
maxCont' maxSum thisSum (x:xs)
  | thisSum + x > maxSum = maxCont' (thisSum + x) (thisSum+x) xs
  | thisSum + x < 0      = maxCont' maxSum 0 xs
  | otherwise            = maxCont' maxSum (thisSum+x) xs

这个疯狂的函数 maxCont' 是什么？ >？让我们对它应该做什么做一个简单的说明。我们希望满足以下条件，前提是 0 ≤ thisSum ≤ maxSum：

maxCont' maxSum thisSum [] = maxSum
maxCont' maxSum thisSum l  = maximum [maxSum, thisSum + maxInit l, maxCont l]

其中 maxInit l 是 l 初始段的最大和> 和maxCont 是l 的最大连续总和。

琐碎但重要的事实：对于所有 l，maxInit l ≤ maxCont l。显然，上述规范保证了 maxCont l = maxCont' 0 0 l，这正是我们想要的。我不会尝试直接解释为什么 maxCont' 的最终版本实现上述规范（我真的不知道该怎么做），而是展示如何从中派生它，一次一步地转换规范，直到它成为代码，那么它肯定是正确的。正如所写，本规范没有给出实现：如果 maxCont 是根据 maxCont' 定义的，如上所述，它将永远循环为 maxCont'< /code> 调用 maxCont 使用相同的列表调用 maxCont'。因此，让我们稍微扩展一下它，以暴露我们需要的部分：

maxCont' maxSum thisSum (x:xs) =
                     maximum [maxSum, thisSum + maxInit (x:xs), maxCont (x:xs)]

这还没有解决任何问题，但它暴露了一些东西。让我们使用它。 thisSum + maxInit (x:xs) 是 thisSum 或 thisSum + x + maxInit xs。但thisSum ≤ maxSum是有前提的，所以我们在计算最大值时可以忽略这种可能性。 maxCont (x:xs) 是包含或不包含 x 的总和。但如果它包含x，那么它和maxInit (x:xs)是一样的，前面已经涵盖了，所以我们可以忽略这种可能性，只考虑maxCont (x:xs) = maxCont xs 的情况。所以我们到达了下一个版本：

maxCont' maxSum thisSum (x:xs) = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]

这个版本最终是正确的递归的，但是我们还有很长的路要走才能获得高效的代码，特别是因为那个神话般的 maxInit 太慢了。让我们将其分解为 Java 代码中考虑的三种情况（稍微滥用 Haskell 表示法）：

maxCont' maxSum thisSum (x:xs)
  | maxSum < thisSum + x     = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]
  | thisSum + x < 0          = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]
  | 0 ≤ thisSum + x ≤ maxSum = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]

在第一种情况下，我们知道 maxSum 不能是最大值：thisSum+x 更大，并且 maxInit xs 始终为正值。在第二种情况下，我们知道 thisSum+x+maxInit xs 不可能是最大值：maxCont xs 始终至少与 maxInit xs< 一样大/code>，并且 thisSum+x 为负数。所以我们可以消除这些可能性：

maxCont' maxSum thisSum (x:xs)
  | maxSum < thisSum + x     = maximum [        thisSum+x+maxInit xs, maxCont xs]
  | thisSum + x < 0          = maximum [maxSum,                       maxCont xs]
  | 0 ≤ thisSum + x ≤ maxSum = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]

现在我们几乎没有足够的优势来扭转局面。现在我们已经消除了不可能的情况，我们将添加一些重复的情况，这会将这三种情况恢复到相同的形式，以便我们可以替换 maxCont' 的原始规范。在第一种情况下，我们没有第一项，因此我们需要使用我们知道不会超过其他项的内容。为了保持 thisSum ≤ maxSum 的不变式，我们需要使用 thisSum+x。在第二种情况下，我们没有像 something+maxInit xs 这样的第二项，但我们知道 maxInit xs ≤ maxCont xs，所以我们可以放心地坚持在0+maxInit xs中。添加这些额外的正则项会产生以下结果：

maxCont' maxSum thisSum (x:xs)
  | maxSum < thisSum + x     = maximum [(thisSum+x), (thisSum+x)+maxInit xs, maxCont xs]
  | thisSum + x < 0          = maximum [maxSum,      0+maxInit xs,           maxCont xs]
  | 0 ≤ thisSum + x ≤ maxSum = maximum [maxSum,      thisSum+x+maxInit xs,   maxCont xs]

最后，检查了前提条件后，我们在规范中进行替换，

maxCont' maxSum thisSum l = maximum [maxSum, thisSum + maxInit l, maxCont l]

以将

maxCont' maxSum thisSum (x:xs)
  | maxSum < thisSum + x     = maxCont' (thisSum+x) (thisSum+x) xs
  | thisSum + x < 0          = maxCont' maxSum 0 xs
  | 0 ≤ thisSum + x ≤ maxSum = maxCont' maxSum (thisSum+x) xs

其修复为真正的语法并附加省略的基本情况产生实际的算法，我们现在已经证明满足该算法规范只要它终止。但每个连续的递归步骤都在较短的列表上运行，因此它确实终止。

为了我的缘故，还有最后一件事要做，那就是更惯用、更灵活地编写最终代码：

maxCont :: (Num a, Ord a) => [a] -> a
maxCont = fst . foldl maxCont' (0,0)
  where
    maxCont' (maxSum, thisSum) x
      | maxSum < newSum = (newSum, newSum)
      | newSum < 0      = (maxSum, 0)
      | otherwise       = (maxSum, newSum)
      where newSum = thisSum + x

Answer 7

我已经尝试过并测试过这一点。如果所有数字都是负数，则返回最大的负数。

测试用例：

{-5, -1, -2, -3, -4}
{ 12, 14, 0, -4, 61, -39}
{2, -8, 3, -2, 4, -10}

代码：

public int FindLargestSum(int[] arr)
{
    int max = Integer.MIN_VALUE;
    int sum = 0;

        for(int i=0; i < arr.length; i++)
        {   
            if(arr[i] > max) max = arr[i];

            sum += arr[i];

            if(sum < 0)
                sum = 0;
            else if(sum > max)
                max = sum;
        }

    return max;
}

Answer 8

我会添加一个包含 2 种方法的答案，以不同的方式处理带有或不带有正元素的数组，用 Java 编写。

---

代码 - Java

MaxSubSum.java:

public class MaxSubSum {
    /**
     * Find max sub array, only include sub array with positive sum.
     * <p>For array that only contains non-positive elements, will choose empty sub array start from 0.
     * <p>For empty input array, will choose empty sub array start from 0.
     *
     * @param arr input array,
     * @return array of length 3, with elements as: {maxSum, startIdx, len};
     * <p>tips: should use 'len' when loop the returned max sub array, so that it could also work for empty sub array,
     */
    public static int[] find(int[] arr) {
        if (arr.length == 0) return new int[]{0, 0, 0}; // empty array, no sub array,

        int maxSum = 0;    // max sum, found so far,
        int maxStart = 0;  // start of max sum,
        int maxLen = 0;    // length of max subarray,

        int sum = 0;  // current sum,
        int start = 0;    // current start,

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > 0) { // get a positive,
                if (sum <= 0) {  // should restart,
                    start = i;
                    sum = arr[i];
                } else sum += arr[i];

                if (sum > maxSum) { // get a larger sum,
                    maxSum = sum;
                    maxStart = start;
                    maxLen = i - start + 1;
                }
            } else sum += arr[i]; // 0 or negative number,
        }

        return new int[]{maxSum, maxStart, maxLen};
    }

    /**
     * Find max sub array, also include sub array with non-positive sum.
     * <p>For array that only contains non-positive elements, will choose first smallest element.
     * <p>For empty input array, will choose empty sub array start from 0.
     *
     * @param arr input array,
     * @return array of length 3, with elements as: {maxSum, startIdx, len};
     * <p>tips: should use 'len' when loop the returned max sub array, so that it could also work for empty sub array,
     */
    public static int[] findIncludeNonPositive(int[] arr) {
        if (arr.length == 0) return new int[]{0, 0, 0}; // empty array, no sub array,

        int maxSum = arr[0];    // max sum, found so far,
        int maxStart = 0;    // start of max sum,
        int maxLen = 1;    // length of max subarray,

        int sum = arr[0];  // current sum,
        int start = 0;    // current start,

        for (int i = 1; i < arr.length; i++) {
            if (sum <= 0) { // should restart,
                start = i;
                sum = arr[i];
            } else sum += arr[i];

            if (sum > maxSum) { // get a larger sum,
                maxSum = sum;
                maxStart = start;
                maxLen = i - start + 1;
            }
        }

        return new int[]{maxSum, maxStart, maxLen};
    }
}

MaxSubSumTest.java:
（测试用例，通过 TestNG）

import org.testng.Assert;
import org.testng.annotations.Test;

import java.util.Arrays;

public class MaxSubSumTest {
    @Test
    public void test_find() {
        Assert.assertTrue(Arrays.equals(MaxSubSum.find(new int[]{-2, -3, 4, -1, -2, 1, 5, -3}), new int[]{7, 2, 5})); // max sub array: {4, -1, -2, 1, 5}
        Assert.assertTrue(Arrays.equals(MaxSubSum.find(new int[]{12, 14, 0, -4, 61, -39}), new int[]{83, 0, 5})); // max sub array: {12, 14, 0, -4, 61}

        // corner
        Assert.assertTrue(Arrays.equals(MaxSubSum.find(new int[]{}), new int[]{0, 0, 0})); // empty array,

        Assert.assertTrue(Arrays.equals(MaxSubSum.find(new int[]{-5, -4, 0, 0, -7, 0, -2}), new int[]{0, 0, 0})); // array with all elements <= 0,
        Assert.assertTrue(Arrays.equals(MaxSubSum.find(new int[]{-5, -4, -2, -7, -2, -9}), new int[]{0, 0, 0})); // array with all elements < 0,
    }

    @Test
    public void test_findIncludeNonPositive() {
        Assert.assertTrue(Arrays.equals(MaxSubSum.findIncludeNonPositive(new int[]{-2, -3, 4, -1, -2, 1, 5, -3}), new int[]{7, 2, 5})); // max sub array: {4, -1, -2, 1, 5}
        Assert.assertTrue(Arrays.equals(MaxSubSum.findIncludeNonPositive(new int[]{12, 14, 0, -4, 61, -39}), new int[]{83, 0, 5})); // max sub array: {12, 14, 0, -4, 61}

        // corner
        Assert.assertTrue(Arrays.equals(MaxSubSum.findIncludeNonPositive(new int[]{}), new int[]{0, 0, 0})); // empty array,

        Assert.assertTrue(Arrays.equals(MaxSubSum.findIncludeNonPositive(new int[]{-5, -4, 0, 0, -7, 0, -2}), new int[]{0, 2, 1})); // array with all elements <= 0,
        Assert.assertTrue(Arrays.equals(MaxSubSum.findIncludeNonPositive(new int[]{-5, -4, -2, -7, -2, -9}), new int[]{-2, 2, 1})); // array with all elements < 0,
    }
}

说明：

• find()
  查找最大子数组，仅包含和为正数的子数组。
  行为：

  • 对于只包含非正元素的数组，会选择从0开始的空子数组。
  • 对于空输入数组，将选择从 0 开始的空子数组。

  顺便说一句：

  • 只有当得到正数且sum <= 0时才重新开始。

• findIncludeNonPositive()
  查找最大子数组，还包括非正数的子数组。
  行为：

  • 对于仅包含非正元素的数组，将选择第一个最小的元素。
  • 对于空输入数组，将选择从 0 开始的空子数组。

  顺便说一句：

  • 只要先前的总和 <= 0，它就会重新启动。
  • 当有多个最大子数组时，它更喜欢从较小的索引开始子数组。
  • 子数组末尾不会包含不必要的 0，这不会改变总和。

复杂度：

• 时间：O(n)
• 空间：O(1)

Answer 9

我们可以使用最简单的两行代码算法，
它很简单，也能处理所有负面的事情:)

curr_max = max(a[i], curr_max+a[i]);

max_so_far = max(max_so_far, curr_max;

例如 C++

int maxSubArraySum(int a[], int size) 
{ 
    int max_so_far = a[0]; 
    int curr_max = a[0]; 

    for (int i = 1; i < size; i++) 
    { 
         curr_max = max(a[i], curr_max+a[i]); 
         max_so_far = max(max_so_far, curr_max; 
    }  
    return max_so_far; 
 }