Overview
This PR adds an implementation of Kadane's Algorithm, an efficient dynamic programming approach to solve the Maximum Subarray Sum problem in O(n) time.
Details
- Problem: Find the contiguous subarray with the maximum sum within a given one-dimensional array of numbers.
- Approach: Dynamic Programming (Kadane’s Algorithm)
- Time Complexity: O(n)
- Space Complexity: O(1)
Implementation Highlights
- Initializes current and global maximum values.
- Iteratively updates the maximum subarray sum ending at each position.
- Tracks the maximum found across all subarrays.
Example
Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6 (Subarray: [4,-1,2,1])
Additional Notes
- Includes basic test cases to validate correctness.
- Code is clean, commented, and easy to follow.
- Can be extended for versions that return the subarray itself, not just the sum.
Overview
This PR adds an implementation of Kadane's Algorithm, an efficient dynamic programming approach to solve the Maximum Subarray Sum problem in O(n) time.
Details
Implementation Highlights
Example
Input:
[-2,1,-3,4,-1,2,1,-5,4]Output:
6(Subarray:[4,-1,2,1])Additional Notes