# 题目 Question

The Maximum Subarray Problem: Suppose you are given an array of n integers. The integers may contain negative numbers. We want to find a (contiguous) subarray whose numbers sum to the most possible. For example, if A= (−5,−6,3,−2,7,−6,2,1), then the maximum subarray would be(3,−2,7)because it sums to 8 and there is no other subarray that sums that high. Solve the problem using divide and conquer, in time O(nlogn).

# 想法 Thinking

Brutal force will consider all possible subarrays, there are $n^2$ subarrays, so the total time is $O(n^2)$ time.

There are three possible ways of locating the ideal (i,j) for the max array:

1. in left half
2. in right half
3. in the region that cross the middle

The third case is not a recursion process. All three cases return the max array for that part.(Correctness).

The termination should be when high == low, return (low, high, A[low ])

After returning three cases, we should do comparison between them.

The recursion should return (lower, higher, sum)

https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-shi-yue-40/

# 运行时间 Run-time

T(n) = 2T(n/2) + O(1) (comparing) + O(n)(cross) + O(1)(sum)

​ = 2T(n/2) + O(n)

​ = O(nlogn) by mastering theorem

おやすみ