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 Java

Could you please assign this issue to me under Hacktoberfest 2023. Thank you!

[shanvijha30]

@fineanmol I would like to work on this issue. Could you please assign it to me under Hacktoberfest 2023. Thank you!

[meenakshi3151]

Sir please assign this issue to me.