Kadane algorithm

#1

question link-https://online.codingblocks.com/player/16974/content/7491/298

how to print the series of sub arrays whose sum is maximum, along with the maximum sum of sub arrays in kadane algo.

#2

Hello @shubhamshagy,

Can you explain the phrase “series of sub-arrays”?

If you are asking,
How to print the sub-array with the maximum sum?

Then, it’s the same as you were taught in previous videos related to this topic.

  1. You have to take two temporary variables, left_index and right_index.

  2. Instead of using the max() function, use the if statement as:

int left_index=0,right_index=0,l,=0;
for(int i=0;i<n;i++){
cs+=a[i];
if(cs<0){
l=i;
cs=0;
}
if(cs>ms){
ms=cs;
left_index=l;
right_index=i;
}

  1. Print the array from left_index to right_index.

Hope, this would help.
Give a like, if you are satisfied.

1 Like
#3

suppose if in an array we got two subarray with maximum sum,then how to print both the sub arrays.
ex-0,1,2,3,4
in this subarray(0,1,2,3,4) and subarray(1,2,3,4) will give maximum sum.

#4

code link–https://ide.codingblocks.com/s/117422

in this kadane alogo at the last the subarray is not getting printed???

#5

Printing all the subarrays with the maximum sum is itself a combination of two different problems:

  1. You have to find the target sum i.e. the maximum sum in your problem.

  2. Printing all the subarrays having target sum.
    example: Print all subarrays with 0 sum.

1 Like
#6

Hey, your code is correct.
It should print the sub-array, but it is not doing that for some specific testcases:
Example:
5
10 -2 3 -5 4
Here the required subarray is:
10 -2 3

So, the left must be 0 and right must be 2.
But, in your code, left is containing some garbage value. Why?
The reason is the value of I,
You have to initialize I=0;
else, left=I; will assign the junk value of I to left causing no output.

Hope, this would help.
Give a like, if you are satisfied.

1 Like