53. Maximum Subarray

medium · array · divide-and-conquer · dynamic-programming · solved 2026.07.13 · 23 sec read

C++

class Solution {public:    int maxSubArray(vector<int>& nums) {        int best = nums[0];        int running_sum = 0;        for (int i = 0; i < nums.size(); i++) {            running_sum = max(nums[i], running_sum + nums[i]);            best = max(running_sum, best);        }        return best;    }};

A little annoying and had done this before. this was just asking/combining both greedy where you have to decide either to add a number to the running sum or just make a new sum that starts at the new number. thats because if the running num is negative but the new number is not, its better to just have a new sum subarray. The data compressions/memozation is just not having to redo the entire sum everytime.