mediumStack
Maximum Subarray Sum Solution
Problem Statement
Given an array of integers, find the maximum sum of a contiguous subarray within the array.
Examples
Example 1:
Input:{"arr":[-2,1,-3,4,-1,2,1,-5,4]}
Output:6
Explanation: The maximum sum of a subarray is [4, -1, 2, 1] which equals 6.
Time: O(n) Space: O(1)
The optimized approach uses Kadane's algorithm, which iterates through the array and at each position finds the maximum sum of the subarray ending at that position, resulting in a time complexity of O(n). This approach is more efficient than the brute-force approach, especially for large arrays.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.