Share my c++ solution with dp and divide and conquer

• DP:

``````int maxSubArray(vector<int>& nums) {
if (nums.size() == 0) return 0;
int thisSum = 0, maxSum = nums[0];
for (int i = 0; i < nums.size(); i++)
{
thisSum += nums[i];
maxSum = thisSum > maxSum ? thisSum : maxSum;
if (thisSum < 0) thisSum = 0;
}

return maxSum;
}
``````

Divide and Conquer:

``````int maxInThree(int a, int b, int c)
{
int maxNum = a > b ? a : b;
maxNum = maxNum > c ? maxNum : c;
return maxNum;
}

int maxSubArraySum(int left, int right, const vector<int>& nums)
{
if (left == right) return  nums[left];
int mid = (left + right) / 2;
int leftMax, rightMax;
int leftBounder = 0, rightBounder = 0;
int leftBounderMax = 0, rightBounderMax = 0;

leftMax = maxSubArraySum(left, mid, nums);
rightMax = maxSubArraySum(mid + 1, right, nums);
leftBounderMax = nums[mid];
for (int i = mid; i >= left; i--)
{
leftBounder += nums[i];
if (leftBounder > leftBounderMax)
leftBounderMax = leftBounder;
}
rightBounderMax = nums[mid+1];
for (int i = mid + 1; i <= right; i++)
{
rightBounder += nums[i];
if (rightBounder > rightBounderMax)
rightBounderMax = rightBounder;
}

return maxInThree(leftMax, rightMax, leftBounderMax + rightBounderMax);

}

int maxSubArray2(vector<int>& nums) {
if (nums.size() == 0) return 0;

return maxSubArraySum(0, nums.size()-1, nums);

}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.