---
# System prepended metadata

title: ADA 2.6 Maximum Subarray
tags: [Maximum Subarray, ADA 2.6]

---

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

取Array中間的連續一段值然後最大化(可得最大值)，最大子序列
![](https://i.imgur.com/BJREYqk.png)
* Example
買股票的買低賣高
寫code的黃金產出時段
![](https://i.imgur.com/ccDRFOI.png)


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

![](https://i.imgur.com/CpOlkjZ.png)

$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)**
有三種可能情形：
![](https://i.imgur.com/im3S61q.png)

In case 3:cross the middle
1.將array分成兩個subarray
2.分別找出兩個array中的maximum subarray
3.將兩個maximum subarray merge
maximum subarray = 3.
![](https://i.imgur.com/g6h1TA0.png)
![](https://i.imgur.com/TkH3v38.png)
所以所花時間 = j-i+1 = i~k 的int數量

## 總整理
![](https://i.imgur.com/1zWHxJ8.png)

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:
![](https://i.imgur.com/pRNRY17.png)

等同於之前的Merge Sort

