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;
}
}
以上代码返回最大子数组的和。
那么如何返回具有最大总和的子数组呢？
这样的东西：
public class Kadane {
double[] maxSubarray(double[] a) {
double max_so_far = a[0];
double max_ending_here = a[0];
int max_start_index = 0;
int startIndex = 0;
int max_end_index = -1;
for(int i = 1; i < a.length; i++) {
if(a[i] > max_ending_here +a[i]) {
startIndex = i;
max_ending_here = a[i];
}
else {
max_ending_here += a[i];
}
if(max_ending_here > max_so_far) {
max_so_far = max_ending_here;
max_start_index = startIndex;
max_end_index = i;
}
}
if(max_start_index <= max_end_index) {
return Arrays.copyOfRange(a, max_start_index, max_end_index+1);
}
return null;
}
}
max_ending_here = Math.max(a[i], max_ending_here + a[i]);
NOT:
max_ending_here = Math.max(0, max_ending_here + a[i]);
if(A.length >= 1){
for(var i = 1;i - UCJava每次启动新的子数组求和时，更新可能的左（起始）索引。一旦更新了max_sum，则更新最终的左和右（结束）。还要维护一个触发器，告诉我们是否创建了新的子数组求和。
int last = 0;
int sum = Integer.MIN_VALUE;
boolean fOrReset = true;
int _L = -1, L = -1, R = -1;
for (int j = 0; j < arr.length; j++) {
last += arr[j];
if (fOrReset) {
_L = j+1;
}
fOrReset = false;
if (sum < last) {
sum = last;
L = _L;
R = j+1;
}
if (last < 0) {
last = 0;
fOrReset = true;
}
}
int main()
{
int a[]={-2, 1, -3, 4, -1, 2, 1, -5, 4};
int size=sizeof(a)/sizeof(a[0]);
int startIndex=0,endIndex=0,i,j;
int max_so_far=0,max_sum=-999;
for(i=0;i<size;i++)
{
max_so_far=max_so_far+a[i];//kadane's algorithm step 1
if(max_so_far>max_sum) //computing max
{
max_sum=max_so_far;
endIndex=i;
}
if(max_so_far<0)
{
max_so_far=0;
startIndex=i+1;
}
}
cout<<max_so_far<<" "<<startIndex<<" "<<endIndex;
getchar();
return 0;
}
一旦您有了起始和结束索引。
for(i=startIndex;i<=endIndex;i++)
{
cout<<a[i];
}
我在一个列表中维护了max_so_far：
for(int i = 0;i<N;i++){
max_end_here = Math.max(seq[i], max_end_here + seq[i]);
sum_list.add(max_end_here);
// System.out.println(max_end_here);
max_so_far = Math.max(max_so_far, max_end_here);
}
然后在列表中搜索最大和，将其索引作为子序列的结尾。 从以该索引为结尾的位置开始向后搜索，找到最后一个值为正数的索引。子序列的起始位置就是这个索引。
for(int i=sum_list.size()-1; i>=0; i--){
if(sum_list.get(i) == max_so_far){
end = i;
while(sum_list.get(i) > 0 && i>=0){
i--;
}
start = (i==-1)?0:i+1;
break;
}
}
另一个C++实现，包括Kadane算法（实际上只是动态规划方法）和扩展Kadane算法，其中包括索引计算和一些注释：
int maxSubArray(vector<int>& nums)
{
int n = nums.size();
if(n == 0) return INT_MIN;
// max sum that ends at index I
int sumMaxI = nums[0];
// total max sum
int sumMax = nums[0];
for(int i = 1; i < n; i++)
{
int curr = nums[i];
// calc current max sum that ends at I
int currSumMaxI = sumMaxI + curr;
// calc new max sum that ends at I
sumMaxI = max(currSumMaxI, curr);
// calc new total max sum
sumMax = max(sumMax, sumMaxI);
}
return sumMax;
}
int maxSubArray_findBeginEnd(vector<int>& nums)
{
int n = nums.size();
if(n == 0) return INT_MIN;
// max sum that ends at index I
int sumMaxI = nums[0];
// start index for max sum (end index is I)
int sumMaxIStart = 0;
// total max sum
int sumMax = nums[0];
// start and end index for total max sum
int sumMaxStart = 0;
int sumMaxEnd = 0;
for(int i = 1; i < nums.size(); i++)
{
int curr = nums[i];
// calc current max sum that ends at I
int currSumMaxI = sumMaxI + curr;
// calc new min sum that ends at I and its starting index
// this part is equal to: sumMaxI = max(currSumMaxI, curr);
// but additionaly enables to save new start index as well
if(curr > currSumMaxI)
{
sumMaxI = curr;
sumMaxIStart = i;
}
else
sumMaxI = currSumMaxI;
// calculate total max sum
// this part is equal to: sumMax = max(sumMax, sumMaxI);
if(sumMaxI > sumMax)
{
sumMax = sumMaxI;
sumMaxStart = sumMaxIStart;
sumMaxEnd = i;
}
// this part is to additionaly capture longest subarray among all that have max sum
// also, of all subarrays with max sum and max len, one with smallest index
// will be captured
else if(sumMaxI == sumMax)
{
if(i - sumMaxIStart > sumMaxEnd - sumMaxStart)
{
sumMaxStart = sumMaxIStart;
sumMaxEnd = i;
}
}
}
// check validity of start and end indices
int checkSum = 0;
for(int i = sumMaxStart; i <= sumMaxEnd; i++)
checkSum += nums[i];
assert(checkSum == sumMax);
// output indices
cout << "Max subarray indices: [" << sumMaxStart << "," << sumMaxEnd << "]" << endl;
return sumMax;
}
我知道这是一个旧的帖子，但是想分享一下我的解决方案版本，以便更清晰地理解。
public static int maxSubArray(int[] a, out int[] subArr){
int sumMax = int.MinValue;
int subSum = 0;
int iLow = 0, iHigh = 0;
for(int i=0; i<a.Length; i++){
subSum+=a[i];
if(subSum>sumMax){
sumMax = subSum;
//move high (upper bound) since sumMax increased
iHigh = i;
//if the subSum is new, then move lower bound
if(subSum == a[i]){
iLow = i;
}
}
subSum = Math.Max(subSum, 0);
}
//build the array - returned as an out parameter
int index = 0;
subArr = new int[iHigh-iLow+1];
while(iLow <= iHigh){
subArr[index++] = a[iLow++];
}
return sumMax;
}
private static int[] applyKadaneAlgorithmGetSubarrayOptimized(int[] input) {
int localMax = input[0];
int globalMax = input[0];
int start = 0;
int end = 0;
for (int i = 1; i < input.length; i++) {
localMax = Math.max(localMax + input[i], input[i]);
if(localMax == input[i]) { //this is similar as --> input[i] > (localMax + input[i])
start = i;
}
if(localMax > globalMax) {
end = i;
}
globalMax = Math.max(localMax, globalMax);
}
//Below condition only occur`enter code here`s when all members of the array are negative integers
//Example: {-9, -10, -6, -7, -8, -1, -2, -4}
if(start > end) {
start = end;
}
return Arrays.copyOfRange(input, start, end + 1);
}
import java.util.Arrays;
public class KadaneSolution4MaxSubArray{
public static void main(String[]args){
int [] array = new int[]{13,-3,-25,20 ,-3 ,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
int[] maxSubArray = maxSubArrayUsingKadaneSol(array);
for(int e : maxSubArray){
System.out.print(e+"\t");
}
System.out.println();
}
public static int[] maxSubArrayUsingKadaneSol(int array[]){
long maxSoFar =array[0];
long maxEndingHere =array[0];
int startIndex = 0;
int endIndex =0;
int j=1;
for(; j< array.length ;j++){
int val = array[j];
if(val >= val+maxEndingHere){
maxEndingHere = val;
startIndex = j;
}else {
maxEndingHere += val;
};
if(maxSoFar < maxEndingHere){
maxSoFar = maxEndingHere;
endIndex = j;
}
}
return Arrays.copyOfRange(array,startIndex,endIndex+1);
}
}
附言：假设给定的数组既是最大子数组问题的候选数组，也不包含所有元素为负数