前往
大廳
主題

LeetCode - 1800. Maximum Ascending Subarray Sum 解題心得

Not In My Back Yard | 2023-01-15 12:00:03 | 巴幣 0 | 人氣 128

題目連結:


題目意譯:
給定一正整數陣列 nums,回傳 nums 中遞增子陣列的總和最大值。

一個子陣列定義為一個陣列中的連續數字之序列。

一子陣列 [numsl, numsl+1, …, numsr-1, numsr] 是遞增的,代表著對於所有 i 值,其中 l ≦ i < r,滿足 numsi < numsi+1。注意到大小為 1 的子陣列視為是遞增的。

限制:
1 ≦ nums.length ≦ 100
1 ≦ nums[i] ≦ 100



範例測資:
範例 1:
輸入: nums = [10,20,30,5,10,50]
輸出: 65
解釋: [5,10,50] 為有著最大總和值 65 的遞增子陣列。

範例 2:
輸入: nums = [10,20,30,40,50]
輸出: 150
解釋: [10,20,30,40,50] 為有著最大總和值 150 的遞增子陣列。

範例 3:
輸入: nums = [12,17,15,13,10,11,12]
輸出: 33
解釋: [10,11,12] 為有著最大總和值 33 的遞增子陣列。


解題思維:
解法很單純——如果現在我們看到 nums[i] > nums[i - 1],則代表以 nums[i - 1] 為結尾的最長遞增子陣列可以延伸到 nums[i] 形成以 nums[i] 作結的最長遞增子陣列。

而當 nums[i] ≦ nums[i - 1] 的話,則代表以 nums[i] 為結尾的最長遞增子陣列即為 nums[i] 本身。

因此我們可以從 S = nums[0] 開始統計子陣列總和。從 nums[1] 開始掃過整個陣列,然後根據以上提見來更新子陣列總和(也就是要嘛 S += nums[i] 或是 S = nums[i])。

而這些總和中的最大值即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作