Maximum Subarray Sum

Solved

Difficulty: Medium Accuracy: — Submissions: 0 Points: 4

Given an array arr[] of integers, find the contiguous subarray (at least one element) with the largest sum and return that sum.

Examples:

Input: arr[] = [2, 3, -8, 7, -1, 2, 3]

Output: 11

Explanation: The subarray [7, -1, 2, 3] has the largest sum, 11.

Input: arr[] = [-2, -4]

Output: -2

Explanation: Every subarray is negative; the best single element is -2.

Constraints:

1 ≤ arr.size() ≤ 10^5
-10^4 ≤ arr[i] ≤ 10^4

Expected Complexities

Time Complexity: O(n) Auxiliary Space: O(1)

Company Tags

Amazon Google Microsoft

Topic Tags

Dynamic Programming Medium

This is Kadane’s algorithm. Scan left to right keeping the best sum of a subarray that ends at the current position: either extend the previous one or start fresh at the current element, whichever is larger. The answer is the largest of those running values. Starting from the first element instead of zero keeps the all-negative case correct.

class Solution {
public:
    long long maxSubarraySum(vector<int>& arr) {
        long long best = arr[0], cur = arr[0];
        for (size_t i = 1; i < arr.size(); i++) {
            cur = max<long long>(arr[i], cur + arr[i]);
            best = max(best, cur);
        }
        return best;
    }
};