###### tags: `ADA 2.6` `Maximum Subarray`
# ADA 2.6 Maximum Subarray

取Array中間的連續一段值然後最大化(可得最大值)，最大子序列
* Example
買股票的買低賣高
寫code的黃金產出時段

## 暴力破解方法 (brute-force solution)
得到 $O(n^2)$ Big O的N平方
*n指的是時間複雜度


$O(n^2)$ = Upper bound

--> Lower bound = Omega(n)
表示至少要把array的值都看過一遍

## Better way: using Divide-and-Conquer solution

* **Base case (n=1)**
maximum subarray = itself

* **Recursive case (n>1)**
有三種可能情形：

In case 3:cross the middle
1.將array分成兩個subarray
2.分別找出兩個array中的maximum subarray
3.將兩個maximum subarray merge
maximum subarray = 3.
所以所花時間 = j-i+1 = i~k 的int數量

## 總整理

base case所花時間: 1 = constant time
recursive case
-case 1 所花時間: k-i+1
-case 2 所花時間: j-k
-case 3 所花時間: j-i+1

## 結論
the running time T(n) of find maximum subarray:

等同於之前的Merge Sort