Re: [問題]n位整數拿掉m數字得到最大數值
※ 引述《PATRICKSTARS (PatrickStar)》之銘言：
: Given an integer (not necessary a decimal number) with n digits, we want to
: remove m (<=n) digits from this number such that the resulting number is as
: large as possible. Design an O(n) time algorithm to solve it.
: 可以提示如何下手嗎?
嗯, 我看了一下.
Range Minimum Query (RMQ) 似乎不太對啊.
舉個簡單的例子好了(有人已經點出來了)
2-3-4-5-1-1, remove 2 digits
RMQ 應該會得到 2-3-4-5,
但這題的最佳解應該是 4-5-1-1.
(希望我沒有誤解你的意思)
我認為這題呢, 要用 increasing sequence 的觀念去看.
從簡單的 case 出發:
1-2-3-4, increasing sequence, so everytime we remove,
we start from begining.
4-3-2-1, decreasing sequence, then we remove from back.
Thus, when we work on it,
we start from making the leading sequence as a decreasing sequence,
then remove the inflection point.
--
趙客縵胡纓，吾鉤霜雪明。銀鞍照白馬，颯沓如流星。
十步殺一人，千里不留行。是了拂衣去，深藏身與名。
閑過信陵飲，脫劍膝前橫。將炙啖朱亥，持觴勸侯贏。
三杯吐然諾，五嶽倒為輕。眼花耳熱後，意氣素霓生。
就趙揮金錘，邯鄲先震驚。千秋二壯士，烜赫大梁城。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 68.181.4.115
討論串 (同標題文章)