Name: Maximum Subarray
Difficulty: Easy
Description: Find the value of the largest contiguous subarray.

Example:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

This one, although simple, tripped me up. I was using Brute Force but it was too slow. I kept getting timeouts. Some of the tests use arrays with over 65,000 elements. I knew it could be done with a running total being compared to max but my head couldn’t wrap around it. What I was missing was clearing the total if we’re below zero – that way the full value of the next number is used:

int maxSubArray(vector<int>& nums) {
    int max = INT_MIN;
    int total = 0;

    for(auto i = nums.begin(); i < nums.end(); ++i) {        
        total += *i;

        if (total > max) {
            max = total;
        }

        if (total < 0) {
            total = 0;
        }
    }

    return max;
}