# O(n) and Divide and Conquer solutions

• O(n) solution :

``````public int maxSubArray(int[] nums) {
if (nums.length == 0) {
return 0;
}

int maxSum = nums[0], currentSum = nums[0];
for (int i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}

return maxSum;
}
``````

Divide and conquer solution :

``````    public int maxSubArray(final int[] nums) {
return maxSubArrayDivideAndConquerHelper(nums, 0, nums.length - 1);
}

private int maxSubArrayDivideAndConquerHelper(final int[] nums, final int start, final int end) {
if (start < end) {
int mid = start + (end - start)/2;
int leftMaxSum = maxSubArrayDivideAndConquerHelper(nums, start, mid);
int rightMaxSum = maxSubArrayDivideAndConquerHelper(nums, mid+1, end);
int crossingMaxSum = maxCrossingSubArraySum(nums, start, end, mid);

if (leftMaxSum >= rightMaxSum && leftMaxSum >= crossingMaxSum) {
return leftMaxSum;
} else if (rightMaxSum >= leftMaxSum && rightMaxSum >= crossingMaxSum) {
return rightMaxSum;
} else {
return crossingMaxSum;
}
} else {
return nums[start];
}
}

private int maxCrossingSubArraySum(final int[] nums, final int start, final int end, final int mid) {
int leftMaxSum = Integer.MIN_VALUE;
int sum = 0;
for (int i = mid; i >= start; i--) {
sum += nums[i];
if (sum > leftMaxSum) {
leftMaxSum = sum;
}
}

int rightMaxSum = Integer.MIN_VALUE;
sum = 0;
for (int i = mid + 1; i <= end; i++) {
sum += nums[i];
if (sum > rightMaxSum) {
rightMaxSum = sum;
}
}

return leftMaxSum + rightMaxSum;
}
``````

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