class Solution {
public:
    int maxSubArray(vector<int>& a) {
        int n = a.size();
        vector<int> dp(n);
        dp[0] = a[0];
        int ans = a[0];
        for (int i = 1; i < n; i ++) {
            dp[i] = max(a[i], dp[i - 1] + a[i]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};