### Binary_ToothLess's blog

By Binary_ToothLess, 7 years ago,

Don't be afraid this is not very difficult....

For new programmer, this is very essential... We know a little bit for that we don't answer many problem as like "largest sum contiguous sub array" that's really very easy to determine largest sum if we know the following algorithm.....

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

Explanation: Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far

Lets take the example:

{-2, -3, 4, -1, -2, 1, 5, -3}

max_so_far = max_ending_here = 0

for i=0, a[0] = -2 max_ending_here = max_ending_here + (-2) Set max_ending_here = 0 because max_ending_here < 0

for i=1, a[1] = -3 max_ending_here = max_ending_here + (-3) Set max_ending_here = 0 because max_ending_here < 0

for i=2, a[2] = 4 max_ending_here = max_ending_here + (4) max_ending_here = 4 max_so_far is updated to 4 because max_ending_here greater than max_so_far which was 0 till now

for i=3, a[3] = -1 max_ending_here = max_ending_here + (-1) max_ending_here = 3

for i=4, a[4] = -2 max_ending_here = max_ending_here + (-2) max_ending_here = 1

for i=5, a[5] = 1 max_ending_here = max_ending_here + (1) max_ending_here = 2

for i=6, a[6] = 5 max_ending_here = max_ending_here + (5) max_ending_here = 7 max_so_far is updated to 7 because max_ending_here is greater than max_so_far

for i=7, a[7] = -3 max_ending_here = max_ending_here + (-3) max_ending_here = 4

Code :

for(int i = 0; i < N; i++){

max_ending_here += Number[i];

if(max_ending_here > max_so_far)max_so_far = max_ending_here;

if(max_ending_here < 0)max_ending_here = 0;

}

So the complexity for this code is O(n)...

Happy coding...:)

• +9

 » 7 years ago, # |   +1 First time I saw this problem I didn't understand very well the idea. Then I saw it was an optimization in memory use. I would like to share the logic behind this optimization.dp[i] -> max value from first position to i For each position: dp[i] = max(dp[i - 1] + Number[i], 0) // This is max_ending_heremaxsingleelement = max(maxsingleelement, Number[i]) // Check case all negative values.Then we will get our solution taking the max dp[i] For each position again:sol = max(sol, dp[i]) // This is max_so_farThis implementation has O(n) in time complexity and memory usage. Then we can use only two variables in the solution you gave us. The complexity will be the same but memory usage will be constant .By the way, what happen when all the elements are negative values? This is a possible case. Based in this case I like to use a variable (maxsingleelement) that stores the max value from each Number[i]. At the end, if this value is lower than 0 then I return maxsingleelement otherwise return sol (max_so_far)
•  » » 7 years ago, # ^ |   0 if it's need to determine the max sum when all input numbers r negative then return the max number which u have but some of the problem needed only positive max_sum...then we will do this... It's a simple things...
 » 7 years ago, # |   0 It will be great if you give links to some problems on this algorithm.
•  » » 7 years ago, # ^ |   0
•  » » » 7 years ago, # ^ |   0 maybe this also http://www.spoj.com/problems/HOTELS/
•  » » » 6 years ago, # ^ |   0 thanks bro for this nice article of yours and also for the problems :)
 » 7 years ago, # |   0 just to fine-tune ur implementation a bit.if the input array is [ - 1,  - 2,  - 2,  - 1,  - 3] (i.e. all negative elements), then ur code would return 0. to have it return  - 1 (i.e. the least negative element) instead, u can initialize max_so_far to  - ∞ instead of 0.
•  » » 5 years ago, # ^ |   0 i think,only doing that will not solve the problem: if (max_ending_here < 0) max_ending_here = 0; this statement needs to be implemented later if (max_so_far < max_ending_here) max_so_far = max_ending_here;
 » 7 years ago, # |   0
•  » » 4 years ago, # ^ |   0 How to solve this problem , Kadane + Update .
 » 6 years ago, # |   0 test case 1: For input array {-2, -3, 4, -1, -2, 1, 5, -3}, the max sum should be 7, with sub-arrary {4, -1, -2, 1, 5} test case 2: For input array {-2, -3, 4, -1, -2, 1, 5, -3, 4}, the max sum should be 8, with sub-array {4, -1, -2, 1, 5, -3, 4}.I tried using the algorithm above, the result of test case 2 still 7 instead 8. Any issue on it?
•  » » 6 years ago, # ^ |   0 Can you show your code?
 » 6 years ago, # |   0 How to implement the same for a 2D array?
•  » » 5 years ago, # ^ |   0 Compute the prefix sums for all rows, then iterate over all pair of colums and for each pair l, r run Kadane's algorithm using prefix[i][r] - prefix[i][l - 1] as array elements.
 » 5 years ago, # |   +10 I find this version slightly easier to understand. Sum for some contiguous sub array can be obtained using partial sums, by subtracting sum at the beginning from sum at the end. To obtain the largest sum you want to subtract as little as possible. So it is necessary to maintain minimum sum that can be subtracted. int min_sum = 0, max_sum = 0; // max_sum = Number[0] to not allow empty sub array int sum = 0; for (int i=0; i < N; i++) { sum += Number[i]; if (sum - min_sum > max_sum) max_sum = sum - min_sum; if (sum < min_sum) min_sum = sum; } 
•  » » 5 years ago, # ^ |   0 when it is all negative numbers we need the max_sum and sum initialized as Number[0] and loop from Number[1] like the code
•  » » » 5 years ago, # ^ |   0 yeah int current_sum=a[0]; int global_sum=a[0]; for(int i=1; i
»
5 years ago, # |
Rev. 2   0

I think this two pointer approach works with O(n) :)

Code:
•  » » 5 years ago, # ^ |   0 you can't apply two pointer because function is not monotonic. There can be negative numbers in the input. just try with input given in the post. Your code outputs 6 whereas ans is 7.
•  » » » 5 years ago, # ^ |   0 Thanks a lot :)I didn't think like that, my bad :(
 » 5 years ago, # |   +31 Three years later, I still can't believe this algorithm has a name.
•  » » 6 weeks ago, # ^ |   +19 It's interesting to know the history behind this problem. We should understand that this all happened during early years of the applied computer science... For example, it includes such now-famous scientists as Michael Shamos and Jon Bentley, who spent 1 week (!) on optimizing an O(n^2) (!) solution for this problem down to O(n log n), using a divide-and-conquer algorithm (!). They also believed for some period of time that it's the best possible solution, given that other similar problems, mostly related to sorting, can't be solved faster than O(n log n). Only some time afterwards Jay Kadane, a statistician, accidentally learned about this problem and the colleagues' solutions and suggested the now-well-known linear-time algorithm.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 It’s actually pretty cool to know that people would historically come up with D&C algorithms to solve the problem before this. You would think D&C would not have existed at all at the time this algorithm was novel.
•  » » » » 6 weeks ago, # ^ |   0 For context, mathematicians have long known about divide-and-conquer algorithms, ex. for block matrix algorithms. John von Neumann invented mergesort in 1945, and Bentley, Haken, and Saxe's famous Master theorem for divide-and-conquer algorithms was published in 1980.
•  » » » 6 weeks ago, # ^ |   0 I had the opportunity to ask Jay Kadane about inventing the algorithm that is his namesake. He is very humble about it and said iirc it was just about being in the right place at the right time in 1977. I guess most people know him for the DP algorithm, which he designed "within a minute" according to Jon Bentley, when the majority of his work is in statistics.
 » 4 years ago, # |   0 How to solve this problem , Kadane + Update .
 » 3 years ago, # | ← Rev. 4 →   -16 Nice one!
 » 2 years ago, # |   0 What if you have to select at least one element? you can't just have zero if it is not present.
•  » » 2 years ago, # ^ |   0 Subarray can be of size 0. So in that case sum is 0.
 » 23 months ago, # |   0 Any bug in it? int kadane(int A[], int n){ int ans = INT_MIN, curr = 0; for(int i = 0; i < n; ++i){ curr = curr + A[i]; ans = max(ans, curr); if(curr < 0) curr = 0; } } 
 » 23 months ago, # |   0 This algorithm can also be derived from the brute force algorithm using Bird-Meertens formalism
 » 18 months ago, # |   0 Can we get all the elements of the maximum subarray by kadane's algorithm??
 » 18 months ago, # |   0 u may want to explain it in yr own words other than simply copying(even the variable names) from geeksforgeeks.
 » 18 months ago, # |   0 Check out this Problem: https://codeforces.com/contest/75/problem/D
 » 5 months ago, # |   -33 Here's a detailed article on Kadane’s algorithm and its problem-solving property to solve the “Maximum Subarray Sum” problem