标签: kadanes-algorithm

我们大多数人都熟悉最大和子阵列问题.我遇到了这个问题的一个变体,要求程序员输出模数为M的所有子阵列总和的最大值.

解决这种变体的天真方法是找到所有可能的子阵列总和(其数量为N ^ 2,其中N是数组的大小).当然,这还不够好.问题是 - 我们怎样才能做得更好？

示例:让我们考虑以下数组:

6 6 11 15 12 1

设M = 13.在这种情况下,子阵列6 6(或12或6 6 11 15或11 15 12)将产生最大总和(= 12).

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
   (a) max_ending_here = max_ending_here + a[i]
   (b) if(max_ending_here < 0)
         max_ending_here = 0
   (c) if(max_so_far < max_ending_here)
          max_so_far = max_ending_here
 return max_so_far

我可以帮助我理解上述算法中最佳的子结构和重叠问题(DP的面包和黄油)吗？

有人可以带我了解Kadane算法中发生的事情吗？想检查我的理解.这是我如何看待它.

你循环遍历数组,每次你将ans变量设置为所看到的最大值,直到该值变为负数,然后ans变为零.

同时,sum变量每次通过循环被覆盖,到之前看到的总和之间的最大值或者到目前为止最大的'ans'.循环执行完毕后,您将获得迄今为止最大的总和或答案!

var sumArray = function(array) {
      var ans = 0;
      var sum = 0;
      //loop through the array.


      for (var i = 0; i < array.length; i++) {
        //this is to make sure that the sum is not negative. 
        ans = Math.max(0, ans + array[i]);

        //set the sum to be overwritten if something greater appears.
        sum = Math.max(sum, ans)
      }

      return sum;

    };

有没有人在功能样式中完成Kadane算法的Scala实现？

有一个A包含(正和负)整数的数组.找到一个(连续的)子数组,其元素的绝对和是最小的,例如:

A = [2, -4, 6, -3, 9]
|(?4) + 6 + (?3)| = 1 <- minimal absolute sum

我已经通过实施蛮力算法,这是开始O(N^2)还是O(N^3),虽然它产生正确的结果.但任务规定:

complexity:
- expected worst-case time complexity is O(N*log(N))
- expected worst-case space complexity is O(N)

经过一番搜索,我认为也许可以修改Kadane的算法以适应这个问题,但我没有做到.

我的问题是 - 卡丹的算法是正确的方法吗？如果没有,你能指出我正确的方向(或命名一个可以帮助我的算法)？我不想要现成的代码,我只需要帮助找到合适的算法.

我在Java中有以下Kadane算法的实现.它基本上是找到连续子阵列的最大总和.

String[] numbers = string.split(",");
                int max_so_far = 0;
                int max_ending_here = 0;
                for (int i = 0; i < numbers.length-1;i++){
                     max_ending_here = max_ending_here + Integer.parseInt(numbers[i]);
                     if (max_ending_here < 0)
                         max_ending_here = 0;
                     if (max_so_far < max_ending_here)
                          max_so_far = max_ending_here;
                }
                System.out.println(max_so_far);

但是,如果数组中存在负数和正数的组合,则此操作无效,例如:

2,3,-2,-1,10

哪个应该返回12作为最大值.截至目前,它返回5

public class Kadane {
  double maxSubarray(double[] a) {
    double max_so_far = 0;
    double 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);
    }
    return max_so_far;
  }
}

上面的代码返回最大子数组的总和.

我怎样才能返回具有最大总和的子数组？

我有以下Kadane算法的实现来解决数组的最大子数组的问题:

public static decimal FindBestSubsequence
    (this IEnumerable<decimal> source, out int startIndex, out int endIndex)
{
    decimal result = decimal.MinValue;
    decimal sum = 0;
    int tempStart = 0;

    List<decimal> tempList = new List<decimal>(source);

    startIndex = 0;
    endIndex = 0;

    for (int index = 0; index < tempList.Count; index++)
    {
        sum += tempList[index];
        if ((sum > result) || 
            (sum == result && (endIndex - startIndex) < (index - tempStart)))
        {
            result = sum;
            startIndex = tempStart;
            endIndex = index;
        } …

例如,我们有

{2,2,-1}, 
when k = 0, return -1.
when k = 3, return 3.

这甚至是棘手的,因为我们有负数和一个额外的变量k.k可以是任何值,负数,不做任何假设.

我不能参考https://en.wikipedia.org/wiki/Maximum_subarray_problem和https://www.youtube.com/watch?v=yCQN096CwWM来解决这个问题.

有谁能够帮我？更好地使用Java或JavaScript.

这是最大的经典算法o(n)(无变量k):

public int maxSubArray(int[] nums) {

        int max = nums[0];
        int tsum = nums[0];
        for(int i=1;i<nums.length;i++){
            tsum = Math.max(tsum+nums[i],nums[i]);
            max = Math.max(max,tsum);
        }

        return max;
    }

我很难理解在我发现的 Kadane 算法的这两个例子中发生了什么。我是 Python 新手，我希望理解这个复杂的算法将帮助我更好地查看/阅读程序。

为什么一个例子比另一个更好，它只是List vs Range吗？还有其他什么可以使示例之一更有效吗？此外，还有一些关于计算中发生了什么的问题。（例子中的问题）

我已经使用PythonTutor帮助我逐步了解到底发生了什么。

示例 1：

在 PythonTuter 中，当您在提供的屏幕截图中选择下一步时，so_far 的值变为 1。这是怎么回事？给出总和，我认为它加上 -2 + 1 即 -1，所以当 so_far 变成 1 时，这是怎么回事？

        def max_sub(nums):
            max_sum = 0
            so_far = nums[0]
        
            for x in nums[1:]:
                so_far = max(x, x + so_far)
                max_sum = max(so_far, max_sum)
            return max_sum
        
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    max_sub(nums)
                6 

示例 2：

与此类似的问题，当我选择 NEXT 步骤时，max_sum 从 -2 变为 4 ......但是如果将元素添加到 2（即 4）中会怎样。对我来说，那将是 -2 + …