53. Maximum Subarray

dp O(n) time O(1) space

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int f = 0, res = INT_MIN;
        for (int x : nums) {
            f = max(f, 0) + x;
            res = max(res, f);
        }
        return res;
    }
};