-
Notifications
You must be signed in to change notification settings - Fork 3.1k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Maximum Subarray Sum: Kadane’s Algorithm #2066
Comments
@DHEERAJHARODE I would like to work on this issue. Could you please assign it to me. |
@DHEERAJHARODE can you please assign this task, i would like to contribute. |
@DHEERAJHARODE please assign to me |
I wish to contribute. Kindly assign me this issue. |
I wish to contribute in this. Kindly assign me this issue. |
please assign this to me |
I wish to contribute. Kindly assign me this issue. |
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!
The text was updated successfully, but these errors were encountered: