LeetCode 1014. 最佳觀光組合

1014. 最佳觀光組合

題目鏈接

題目分析

題目給定的觀光景點(diǎn)評(píng)分公式是dp = A[i] + A[j] + i - j督怜,變化一下可以得到A[i] + iA[j] - j滨达。

我們可以發(fā)現(xiàn)轻黑,在遍歷的過(guò)程中,只要固定了ij,前后兩個(gè)式子就不會(huì)變。所以我們可以遍歷原數(shù)組森逮,在遍歷的過(guò)程中不斷更新A[i] + i的最大值以及dp

遍歷過(guò)程如下:

for (int i = 1; i < A.size(); i++) {
    res = res > temp + A[j] - j ? res : temp + A[j] - j;
    temp = temp > A[j] + j ? temp : A[j] + j;
}

最后返回res即可磁携。

題目解答

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& A) {
        int res = INT_MIN;
        int temp = A[0] + 0;
        for (int j = 1; j < A.size(); j++) {
            res = res > temp + A[j] - j ? res : temp + A[j] - j;
            temp = temp > A[j] + j ? temp : A[j] + j;
        }
        return res;
    }
};
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末褒侧,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子谊迄,更是在濱河造成了極大的恐慌闷供,老刑警劉巖,帶你破解...
    沈念sama閱讀 206,602評(píng)論 6 481
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件统诺,死亡現(xiàn)場(chǎng)離奇詭異歪脏,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)粮呢,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,442評(píng)論 2 382
  • 文/潘曉璐 我一進(jìn)店門(mén)婿失,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人啄寡,你說(shuō)我怎么就攤上這事豪硅。” “怎么了挺物?”我有些...
    開(kāi)封第一講書(shū)人閱讀 152,878評(píng)論 0 344
  • 文/不壞的土叔 我叫張陵懒浮,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我识藤,道長(zhǎng)砚著,這世上最難降的妖魔是什么次伶? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 55,306評(píng)論 1 279
  • 正文 為了忘掉前任,我火速辦了婚禮稽穆,結(jié)果婚禮上冠王,老公的妹妹穿的比我還像新娘。我一直安慰自己秧骑,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 64,330評(píng)論 5 373
  • 文/花漫 我一把揭開(kāi)白布扣囊。 她就那樣靜靜地躺著乎折,像睡著了一般。 火紅的嫁衣襯著肌膚如雪侵歇。 梳的紋絲不亂的頭發(fā)上骂澄,一...
    開(kāi)封第一講書(shū)人閱讀 49,071評(píng)論 1 285
  • 那天,我揣著相機(jī)與錄音惕虑,去河邊找鬼坟冲。 笑死,一個(gè)胖子當(dāng)著我的面吹牛溃蔫,可吹牛的內(nèi)容都是我干的健提。 我是一名探鬼主播,決...
    沈念sama閱讀 38,382評(píng)論 3 400
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼伟叛,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼私痹!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起统刮,我...
    開(kāi)封第一講書(shū)人閱讀 37,006評(píng)論 0 259
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤紊遵,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后侥蒙,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體暗膜,經(jīng)...
    沈念sama閱讀 43,512評(píng)論 1 300
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 35,965評(píng)論 2 325
  • 正文 我和宋清朗相戀三年鞭衩,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了学搜。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,094評(píng)論 1 333
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡论衍,死狀恐怖恒水,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情饲齐,我是刑警寧澤钉凌,帶...
    沈念sama閱讀 33,732評(píng)論 4 323
  • 正文 年R本政府宣布,位于F島的核電站捂人,受9級(jí)特大地震影響御雕,放射性物質(zhì)發(fā)生泄漏矢沿。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,283評(píng)論 3 307
  • 文/蒙蒙 一酸纲、第九天 我趴在偏房一處隱蔽的房頂上張望捣鲸。 院中可真熱鬧,春花似錦闽坡、人聲如沸栽惶。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,286評(píng)論 0 19
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)外厂。三九已至,卻和暖如春代承,著一層夾襖步出監(jiān)牢的瞬間汁蝶,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 31,512評(píng)論 1 262
  • 我被黑心中介騙來(lái)泰國(guó)打工论悴, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留掖棉,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 45,536評(píng)論 2 354
  • 正文 我出身青樓膀估,卻偏偏與公主長(zhǎng)得像幔亥,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子察纯,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 42,828評(píng)論 2 345