12_6最長(zhǎng)上升子序列LIS

這是一個(gè)經(jīng)典的LIS(即最長(zhǎng)上升子序列)問(wèn)題,請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡量?jī)?yōu)的解法求出序列的最長(zhǎng)上升子序列的長(zhǎng)度搔体。

給定一個(gè)序列A及它的長(zhǎng)度n(長(zhǎng)度小于等于500)恨樟,請(qǐng)返回LIS的長(zhǎng)度。

測(cè)試樣例:
[1,4,2,5,3],5
返回:3

class LongestIncreasingSubsequence {
public:
    int getLIS(vector<int> A, int n) {
        // write code here
        vector<int> dp(n, 0);
        dp[0] = 1;
        int lis = 0;
        for(int i=1; i<n; ++i){
            int base = 0;
            for(int j=i-1; j>=0; --j){
                if(A[i] > A[j]){
                    base = dp[j] > base ? dp[j] : base;
                }
            }
            dp[i] = base + 1;
            lis = dp[i] > lis ? dp[i] : lis;
        }
        return lis;
    }
};

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末疚俱,一起剝皮案震驚了整個(gè)濱河市劝术,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌呆奕,老刑警劉巖养晋,帶你破解...
    沈念sama閱讀 206,126評(píng)論 6 481
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異梁钾,居然都是意外死亡绳泉,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,254評(píng)論 2 382
  • 文/潘曉璐 我一進(jìn)店門姆泻,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)零酪,“玉大人冒嫡,你說(shuō)我怎么就攤上這事∷奈” “怎么了孝凌?”我有些...
    開封第一講書人閱讀 152,445評(píng)論 0 341
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)月腋。 經(jīng)常有香客問(wèn)我蟀架,道長(zhǎng),這世上最難降的妖魔是什么罗售? 我笑而不...
    開封第一講書人閱讀 55,185評(píng)論 1 278
  • 正文 為了忘掉前任辜窑,我火速辦了婚禮,結(jié)果婚禮上寨躁,老公的妹妹穿的比我還像新娘。我一直安慰自己牙勘,他們只是感情好职恳,可當(dāng)我...
    茶點(diǎn)故事閱讀 64,178評(píng)論 5 371
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著方面,像睡著了一般放钦。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上恭金,一...
    開封第一講書人閱讀 48,970評(píng)論 1 284
  • 那天操禀,我揣著相機(jī)與錄音,去河邊找鬼横腿。 笑死颓屑,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的耿焊。 我是一名探鬼主播揪惦,決...
    沈念sama閱讀 38,276評(píng)論 3 399
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼罗侯!你這毒婦竟也來(lái)了器腋?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 36,927評(píng)論 0 259
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤钩杰,失蹤者是張志新(化名)和其女友劉穎纫塌,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體讲弄,經(jīng)...
    沈念sama閱讀 43,400評(píng)論 1 300
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡措左,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 35,883評(píng)論 2 323
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了垂睬。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片媳荒。...
    茶點(diǎn)故事閱讀 37,997評(píng)論 1 333
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡抗悍,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出钳枕,到底是詐尸還是另有隱情缴渊,我是刑警寧澤,帶...
    沈念sama閱讀 33,646評(píng)論 4 322
  • 正文 年R本政府宣布鱼炒,位于F島的核電站衔沼,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏昔瞧。R本人自食惡果不足惜指蚁,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,213評(píng)論 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望自晰。 院中可真熱鬧凝化,春花似錦、人聲如沸酬荞。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,204評(píng)論 0 19
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)混巧。三九已至枪向,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間咧党,已是汗流浹背秘蛔。 一陣腳步聲響...
    開封第一講書人閱讀 31,423評(píng)論 1 260
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留傍衡,地道東北人深员。 一個(gè)月前我還...
    沈念sama閱讀 45,423評(píng)論 2 352
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像聪舒,于是被迫代替她去往敵國(guó)和親辨液。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 42,722評(píng)論 2 345

推薦閱讀更多精彩內(nèi)容

  • 描述 給定一個(gè)整數(shù)序列箱残,找到最長(zhǎng)上升子序列(LIS)滔迈,返回LIS的長(zhǎng)度。 說(shuō)明 最長(zhǎng)上升子序列的定義:最長(zhǎng)上升子序...
    6默默Welsh閱讀 680評(píng)論 1 0
  • 問(wèn)題定義: 給定一個(gè)長(zhǎng)度為N的數(shù)組被辑,找出一個(gè)最長(zhǎng)的單調(diào)自增子序列(不一定連續(xù)燎悍,但是順序不能亂)。例如:給定一個(gè)長(zhǎng)度...
    miltonsun閱讀 1,060評(píng)論 0 1
  • 對(duì)于下面一個(gè)序列: 2盼理,1谈山,5,3宏怔,6奏路,4畴椰,8,9鸽粉,7 求其最長(zhǎng)遞增子序列(可以不連續(xù)但順序不可變) 解法一:動(dòng)態(tài)...
    LamyGoGoGo閱讀 1,196評(píng)論 0 0
  • 給定一個(gè)整數(shù)序列斜脂,找到最長(zhǎng)上升子序列(LIS),返回LIS的長(zhǎng)度触机。 說(shuō)明 最長(zhǎng)上升子序列的定義: 最長(zhǎng)上升子序列問(wèn)...
    Arnold134777閱讀 1,003評(píng)論 0 0
  • 題目 給定一個(gè)整數(shù)序列帚戳,找到最長(zhǎng)上升子序列(LIS),返回LIS的長(zhǎng)度儡首。 說(shuō)明最長(zhǎng)上升子序列的定義:最長(zhǎng)上升子序列...
    六尺帳篷閱讀 277評(píng)論 0 1