Reference: LeetCode

Difficulty: Easy

My Post: Easy-Understand Java Solutions with Explanations (B-F, Divide-And-Conquer, DP)

## Problem

Given an integer array

`nums`

, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

**Example:**

1 | Input: [-5] |

**Follow up:** If you have figured out the $O(N)$ solution, try coding another solution using the divide and conquer approach, which is more subtle.

## Analysis

### Most Stupid Solution

For each element, we construct all possible subarrays starting from this element. Totally there are at most $N^2$ subarrays. Also, calculating the sum of each subarray takes $O(N)$.

1 | public int maxSubArray(int[] nums) { |

**Time:** $O(N^3)$**Space:** $O(1)$

### Brute-Force

Why did you calculate the sum separately?

**Note:** In the inner loop, start from `i + 1`

. Don’t initialize `sum`

as $0$ and start from `i`

.

1 | public int maxSubArray(int[] nums) { |

**Time:** $O(N^2)$**Space:** $O(1)$

### Divide and Conquer

Divide-and-conquer consider 3 cases:

**Case 1:**Subarray in the left half ->`leftSum`

**Case 2:**Subarray in the right half ->`rightSum`

**Case 3:**Subarray crosses the middle ->`crossSum`

We need to compare three max values: `leftSum`

, `rightSum`

, and `crossSum`

. By constructing the `crossSum`

, we propagate from the right-end of the left subarray `[lo, mid]`

and from the left-end of the right subarray `[mid + 1, hi]`

. In each direction, we are continuously updating the maximum sum.

1 | // Example |

**BTW, Index lo/hi/mid Caveat:**

Write the condition as `if (lo == hi)`

(stops at one element) or `if (lo >= hi)`

(stops at $0$ element). Why?

Write the subproblem as `[lo, mid]`

and `[mid + 1, hi]`

, which is not like binary search (`hi = mid - 1`

and `lo = mid + 1`

).

1 | public int maxSubArray(int[] nums) { |

Another version, initialize sums and max values as the first element.

1 | private int crossSum(int[] nums, int lo, int hi, int mid) { |

**Time:** $O(N\log{N})$ since $T(N) = 2T(N/2) + O(N)$.**Space:** $O(\log{N})$

### DP

Suppose we know the maximum subarray ending at $i$ (inclusive). We denote `SUM(i)`

as the maximum sum of a subarray ending at index $i$ and denote `OPT(i)`

as the maximum sum in the subarray $[0, i]$. Our final result is `OPT(n - 1)`

. (notice the difference since it is very trivial)

For an element `nums[i]`

, we have two choices: Appending it to a previous subarray `SUM(i - 1)`

or start a new subarray from itself. Then we can write the recurrence for `SUM(i)`

and `OPT(i)`

as follows:

`SUM(i)`

= max(`SUM(i - 1) + nums[i]`

, `nums[i]`

)`OPT(i)`

= max(`OPT(i - 1)`

, `SUM(i)`

).

Note: `OPT`

is updated when a larger `SUM[i]`

is discovered.

The initial values are `SUM(0) = nums[0]`

and `OPT(0) = nums[0]`

. We can do it in one pass. So here is the code:

1 | public int maxSubArray(int[] nums) { |

Since `SUM(i)`

and `OPT(i)`

could be calculated by the previous values, we don’t need arrays of size $n$ to store all information. Here is the code that reduces the space complexity:

1 | public int maxSubArray(int[] nums) { |

**Time:** $O(N)$**Space:** $O(1)$