#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> d(n+1,vector<int>(n+1));
        int maxx = -0xff;
        for(int i = 0;i<n;i++)
        {
            d[i][i] = nums[i];
            maxx = max(nums[i],maxx);
        }
        for(int i = 0;i<n;i++)
        {
            for(int j = i+1;j<n;j++)
            {
                d[i][j] = d[i][j-1]+d[j][j];
                maxx = max(maxx,d[i][j]);
            }
        }
        return maxx;
    }
};
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxx = -0xff;
        int sum = 0;
        for(auto e:nums)
        {
            if(sum<0)
            {
                sum = e;
            }else
            {
                sum +=e;
            }
            maxx = max(sum,maxx);
        }
        return maxx;
    }
};
int main()
{
    return 0;
}