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;
}