Maximum Subarray Sum
Medium Acceptance 36.28% Points 30.00
You are given an integer array arr[]. Find and return the maximum sum possible from all the subarrays
Examples
Example 1
Example 1
Input: arr[] = [1, 2, 3, -2, 5]
Output: 9
Explanation: Max subarray sum is 9 of elements (1, 2, 3, -2, 5).
Example 2
Example 2
Input: arr[] = [-1, -2, -3, -4]
Output: -1
Explanation: Max subarray sum is -1 of element (-1).
Example 3
Example 3
Input: arr[] = [5, 4, 7]
Output: 16
Explanation: Max subarray sum is 16 of elements (5, 4, 7)
Hints
Hint 1
Expected Time Complexity: O(n)
Hint 2
Expected Auxiliary Space: O(1)
Constraints
- 1 <= arr.size() <= 10^5
- -109 <= arr[i] <= 104
Companies
Amazon Microsoft Visa Walmart Google + 4 more
Track your submissions
Please log in to review your progress and explore code submissions from other participants.
Unlock the full solution
Please log in to access detailed answers and explanations.
Join the discussion
Please log in to join conversations with other participants.