Leetcode coding challenge notes

Question: Maximum Subarray

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
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

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.

Notes

A clever way to solve this kind of question is:

  1. Remember that the subarray must be contiguous, and sum is the largest one.

  2. key idea is : we calculate the sum starting from the first element of the array, if the previous sum plus the current array element less than the current array element, then we should recalculate the sum starting from the current array element.

    More explanation:

    if sum + num[i] < num[i], then we need to drop current sum (because we can’t get the largest sum since “sum + num[i]” is less than num[i] itself. If we can’t plus a number that can make the current number greater, then there is meaningless to do that for this question).

    After drop the sum, we recalculate the sum starting from current array element “num[i]”.

A more reliable way to solve this question is using Divide and conquer and DFS:

The key idea of Divide and conquer is to turn a big problem into a number of small problems.

Consider that if we divide the array nums[] into two subarray equally: nums_a and nums_b, then there are only three possibilities where the targeted subarray can be:

  1. the subarray is completely in nums_a.

  2. the subarray is completely in nums_b.

  3. the subarray cross nums_a and nums_b.

We can use DFS to implement this process. And another key point is to figure out how to solve the situation that the subarray cross nums_a and nums_b.

​ The main idea is to find the largest value starting from the middle value of the original array to the left and right respectively.

[-2,1,-3,4,-1,2,1,-5,4]

​ right<—— -1——>left

right maximum + left maximum = maximum(the subarray cross nums_a and nums_b)

More detailed explanation