kadane算法的java [英] kadane algorithm in java

问题描述

我有Kadane的算法在java中的以下实现。它基本上是找到连续的子阵的最高金额。

I have the following implementation of Kadane's algorithm in java. It is basically to find the maximum sum of contiguous subarray.

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

然而这不工作，如果有的负和正数以阵列的组合，例如下列：

However this doesn't work if there is a combination of a negative and positive number in an array, for example the following:

2,3,-2,-1,10

这应该返回12为最大。截至目前，它返回5

Which should return a 12 as a maximum. As of now it returns 5

推荐答案

您算法的实现看起来不错，但你的循环条件 I＆LT; numbers.length-1 不：不动为止只有1短数组的结束。 I＆LT; numbers.length 应该这样做： - ）

You algorithm implementation looks ok, but your loop conditional i < numbers.length-1 does not: it stops just 1 short of the end of the array. i < numbers.length should do it :-)

这篇关于kadane算法的java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！