53. Maximum Subarray

53.cpp

#include <iostream>
#include <vector>

using namespace std;

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

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    Solution s;
    cout << s.maxSubArray(nums) << endl;
    return 0;
}