# Share my DP and Divide and Conquer

• the O(n) of DP

``````public int maxSubArray(int[] nums) {
int len = nums.length, dp = nums[0], max = dp;
for (int i = 1; i < len; ++i) {
dp = nums[i] + (dp > 0 ? dp : 0);
if (dp > max) max = dp;
}
return max;
}
``````

the O(n) of Divide and Conquer

``````public int maxSubArray(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
private int helper(int[] nums, int left, int right) {
if (left >= right) return nums[left];
int mid = (left + right) >> 1;
int leftAns = helper(nums, left, mid);
int rightAns = helper(nums, mid + 1, right);
int leftMax = nums[mid], rightMax = nums[mid + 1];
int temp = 0;
for (int i = mid; i >= left; --i) {
temp += nums[i];
if (temp > leftMax) leftMax = temp;
}
temp = 0;
for (int i = mid + 1; i <= right; ++i) {
temp += nums[i];
if (temp > rightMax) rightMax = temp;
}
return Math.max(Math.max(leftAns, rightAns), leftMax + rightMax);
}
``````

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