資料科學小嫩嫩 10/18 - Day 22 Leetcode 53. Maximum Subarray
前篇: 資料科學小嫩嫩 10/13 - Day 20 Leetcode 90. Subset II
--
使用所說的 DP 累加法
Leetcode 121 Best time to buy and sell stock
同樣類似上述 DP 方式 來做即可
(攤平法? 當有價格更低時, 就再買? XD)
Leetcode 152 Maximum product subarray
這邊實際在 github 是另外寫了一個 get_minmax() 來節省處理 pair 的時間.
Leetcode 697 degree of an array
可用同樣 DP 方法處理, 要注意出現頻率最多的數字可能有多個.
直接用 int array 速度上會比 vector<int> 快. 但較佔記憶體
要節省記憶體的話, 可以直接用 freq 的 hash map 來找出 頻率出現最多的數字
Leetcode 1749 maximum absolute sum of any subarray
發現中高等題目的, 會和 數學 或 題目轉換聯想有關.
這題和先前不同的是, 是取絕對值, 也就是連續的負數有可能是最大值.
可以想成同方向移動的最大距離,
陣列可以想成每秒移動距離,
x 軸是陣列 index, y 軸是位置. 一開始在零的位置
> 0 : y 軸 正向移動
< 0 : y 軸 負向移動.
這樣就會得到一個 波型.
mx 是最高峰, my 是最底峰.
mx - my 這段就會是相對位置的最大距離. 也就是 subarray 相加的絕對值最大值.
留言
張貼留言