public:
int maxSubArray(vector<int>& nums) {
int sum = nums[0];
int MAX = nums[0];
for (int i = 1; i < nums.size(); i++)
{
sum = max(nums[i], sum + nums[i]);
if (sum > MAX)
MAX = sum;
}
return MAX;
}
int maxDarray(vector<int>& a)
{
if (a.size() == 0)
{
return 0;
}
vector<int> left;
vector<int> right;
int max1, max2, MAX = INT_MIN;
for (int k = 1; k < a.size() - 1; k++)
{
left.assign(a.begin(), a.begin() + k);
right.assign(a.begin() + k, a.end());
max1 = maxSubArray(left);
max2 = maxSubArray(right);
MAX = max(MAX, max1 + max2);
}
return MAX;
}
};