How to return maximum sub array in Kadane's algorithm?

find all contiguous subarrays of an array
maximum sum subarray divide and conquer
maximum subarray sum hackerrank solution
largest sum non contiguous subarray
largest sum contiguous subarray in c
kadane's-algorithm 2d
maximum subarray - leetcode
largest sum contiguous subarray dynamic programming
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;
  }
}

The above code returns the sum of the maximum sub-array.

How would I instead return the sub-array which has the maximum sum?

Something like this:

public class Kadane {
  double[] maxSubarray(double[] a) {
    double max_so_far = 0;
    double max_ending_here = 0;
    int max_start_index = 0;
    int startIndex = 0;
    int max_end_index = -1;

    for(int i = 0; i < a.length; i++) {
      if(0 > max_ending_here +a[i]) {
        startIndex = i+1;
        max_ending_here = 0;
      }
      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;
  }
}

Maximum Subarray Sum using Divide and Conquer algorithm , Maximum Subarray Problem (Kadane's algorithm). Given an array of integers, find contiguous subarray within it which has the largest sum. For example,. KADANE's algorithm. Initialize two variables named CS (current sum) and MS (max sum) with 0. Loop for each element of the array and do these below tasks for each iteration, CS = CS + ar[i] If(CS<0) then CS=0. (C) If(MS<CS) then MS=CS.

The code above has an error. Should be:

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 not, would fail for a sequence such as: 2 , 4, 22, 19, -48, -5 , 20, 40 and return 55 instead of the correct answer of 60.

SEE Kadane algorithm at http://en.wikipedia.org/wiki/Maximum_subarray_problem

Maximum Subarray Problem (Kadane's algorithm), Something like this: public class Kadane { double[] maxSubarray(double[] a) { double max_so_far = 0; double max_ending_here = 0; int max_start_index = 0;  We can easily solve this problem in linear time using kadane’s algorithm. The idea is to maintain maximum (positive sum) sub-array “ending” at each index of the given array. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous index.

I maintain the max_so_far in a list:

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

Then search the biggest sum in list, its index as sub sequnece end. Start from index as end and search backwards, find the last index whose value is positive. Subsequence start is this index.

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

Max Contiguous Subarray Sum, Kadane's algorithm is able to find the maximum sum of a contiguous subarray in an array with a runtime of O(n). Product of all Subarrays of an Array; Sliding Window Maximum : Set 2; Count of subsets with sum equal to X; Maximum number of unique values in the array after performing given operations; Check if sum of Fibonacci elements in an Array is a Fibonacci number or not; Calculate the Sum of GCD over all subarrays; Longest sub-array with maximum GCD

A more easier approach closely linked to the algorithm.

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

Once you have start and End index.

for(i=startIndex;i<=endIndex;i++)
{
cout<<a[i];
}

How to return maximum sub array in Kadane's algorithm?, Kadane's Algorithm – Maximum Subarray Problem. Objective: The maximum subarray problem is the task of finding the contiguous subarray within a one-  Kadane’s Algorithm – Maximum Subarray Problem Objective: The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum.

we can keep track max subarray by using following code :

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

P.S. Assume that given array is candidate of Max sub array problem as well as not having all elements negative

Kadane's Algorithm — (Dynamic Programming), Grenander was looking to find a rectangular subarray with maximum sum, in a two-dimensional array of real numbers. A  Kadane’s Algorithm: The idea is to keep scanning through the array and calculating the maximum sub-array that ends at every position. The sub-array will either contain a range of numbers if the array has intermixed positive and negative values, or it will contain the least negative value if the array has only negative values.

Kadane's Algorithm, The maximum subarray problem is a task to find the series of contiguous Kadane's algorithm is a popular solution to the maximum subarray  class Main {// Function to print contiguous subarray with the largest sum // in given set of integers public static void kadane(int[] A) {// stores maximum sum sub-array found so far

Maximum subarray problem, Given an integer array nums , find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1  Sub Array with Maximum Sum – Kadane Algorithm is the best solution. Find the sub array with maximum sum. Maximum sum sub array. Sub array with maximum sum. Largest Sum Contiguous Subarray. This can be solved using Kadane’s Algorithm which is a Dynamic Programming approach. Find the sum of contiguous subarray in an array of numbers which has

Maximum Subarray Problem, The maximum subarray problem was proposed by Ulf Grenander in 1977 as a simplified model for maximum likelihood estimation of patterns in digitized images. [5] Grenander was looking to find a rectangular subarray with maximum sum, in a two-dimensional array of real numbers.

Comments
  • Do you mean max sub array starting at index 0?
  • its not necessary that max sub array start at index 0, it depends on the array values
  • The condition should be "if(0 >=max_ending_here+a[i]) not just > to make it work for arrays like: {5,2,-4,3,2,-8,7,6,-1,-2,3,-50}
  • +1 Good test case. I took a look into this, I think you meant if(max_ending_here >= max_so_far). However, it isn't clear that a longer max subarray is any more or less correct than a shorter one.
  • Can you please explain why we need both max-start-index and start-index ? Can we get rid of max-start-index?
  • @user911 - I took a look and cannot figure out a clean way to get rid of one or the other without replacing it with another variable. That does not mean though it is not possible. Ultimately we do want the "start index of the max subarray" i.e. the max_start_index. What did you have in mind? Some of the test cases I thought through were {5,2,-8, 1, 7} and {5, -4, 2, 1}
  • This doesn't work for an array will all negative numbers Example {-6,-9,-3,-5-2}
  • It is correct. max(a[i], max_ending_here + a[i]) is only for an array with all negative values.
  • @AndrejKaurin you might want to change your code to if(A.length >= 1){ for(var i = 1;i<A.length;i++) { var x = A[i]; max_ending_here = Math.max(0, max_ending_here + x); max_so_far = Math.max(max_so_far, max_ending_here); } }
  • Can you please clarify what you are trying to know, what problem you are facing and what have you tried so far?