Maximum Subarray Sum: Kadane’s Algorithm

[shanvijha30]

Feature :

There is a well-known problem Maximum Subarray Sum, in which we have to find a contiguous subarray whose sum is maximum among all the subarrays for the given array. To solve this one must know about Kadane’s Algorithm. Kadane’s Algorithm is an iterative dynamic programming algorithm.

Kadane's Algorithm is an iterative dynamic programming algorithm ( A method that is often used to solve finite-dimensional nonlinear constrained global optimal control problems ), so to understand Kadane's Algorithm we need to understand Dynamic Programming first. Kadane's Algorithm is used to solve the famous problem - Maximum Subarray Sum. This Algorithm is used to solve the problem in linear time.

Input: [-3, -4, 5, -1, 2, -4, 6, -1] Output: 8 Explanation: Subarray [5, -1, 2, -4, 6] is the max sum contiguous subarray with sum 8.

Approach :

The simple approach to solve this problem is to run two for loops and for every subarray check if it is the maximum sum possible. Follow the below steps to solve the problem.

Run a loop for i from 0 to n – 1, where n is the size of the array. Now, we will run a nested loop for j from i to n – 1 and add the value of the element at index j to a variable currentMax. Lastly, for every subarray, we will check if the currentMax is the maximum sum of all contiguous subarrays.

Will add Maximum Subarray Sum: Kadane’s Algorithm with adequate comments and proper documentation for readers to get a clear understanding. To be added in C++ and Java @DHEERAJHARODE Could you please assign this issue to me under Hacktoberfest 2023. Thank you!

[shanvijha30]

@DHEERAJHARODE I would like to work on this issue. Could you please assign it to me. Thank you!

[Jugnu-Gupta]

@DHEERAJHARODE can you please assign this task, i would like to contribute. The idea of Kadane’s algorithm is to maintain a variable max_ending_here that stores the maximum sum contiguous subarray ending at current index and a variable max_so_far stores the maximum sum of contiguous subarray found so far, Everytime there is a positive-sum value in max_ending_here compare it with max_so_far and update max_so_far if it is greater than max_so_far.

[arunbossakkk]

@DHEERAJHARODE please assign to me

[Ashima2003]

I wish to contribute. Kindly assign me this issue.

[PeeyushRathore]

I wish to contribute in this. Kindly assign me this issue.

[devyani277]

please assign this to me

[Ashima2003]

I wish to contribute. Kindly assign me this issue.

[Arhaan-P]

@DHEERAJHARODE Please assign this to me