720 - C++ LeetCode

【Leetcode】C++ - [53] Contains Duplicate 個人解法筆記 (內含範例程式碼) 內含 C++ vector max 用法整理

題目出處

53. Maximum Subarray

難度

Easy

題目分類

array, divide-and-conquer, dynamic-programming

個人範例程式碼

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp;
        for(int i=0; i< nums.size(); i++){
            if(i == 0){
                dp.push_back(nums[i]); // record 'include me' biggest
            }
            else{
                dp.push_back((nums[i] > nums[i]+dp[i-1]) ? nums[i] : nums[i]+dp[i-1]); // record 'include me' biggest
            }
        }      
        auto it = std::max_element(dp.begin(), dp.end());  
        // std::vector<int>::iterator it;
        // cout << *it << endl;

        // int max_value = *std::max_element(dp.begin(), dp.end());
        // cout << max_value << endl;

        return *it;
    }
};

說明

這題我使用的是 DP 的解法，
我宣告一個 DP 來儲存「包含自己的」時最好的答案。

換句話說，我將題目拆解成到「包含每一個 index 的當下」 都是一個小題目，將題目的答案儲存進 dp 中。

注意是「包含自己」的最好答案，也就是說，我們只需要比較「自己」與「dp(n-1)+自己」誰比較大。
DP 裡面都是「一定要包含自己的最佳解」，而不是「全域的最佳解」。

所以假設原來的題目變成：
nums = [1,2,-1,4]
dp = [1,3,2,6]

2 就是因為一定要包含「-1」，我們只有「-1」跟「-1+‘包含前一個’的最大」誰比較大。

C++ vector max 用法整理

vector 想必是 C++ 最常被使用的資料型態了。
因此如何取 max 我們應該也要來好好記錄一下

以下方法基本上兩者大同小異，但因為 vector 需要透過 iterator 遍歷，
這邊就沒有像 python 那麼方便了。

vector 取 max 方法一 - iterator

基本上就是很標準的寫法，使用的是 std 裡面定義的 std::max_element，
會回傳位址，需要用 *it 取得該值。

vector<int> dp;
auto it = std::max_element(dp.begin(), dp.end());  
// std::vector<int>::iterator it;
cout << *it << endl;

註：這邊的 「auto it」 等於 「std::vector::iterator it」，
宣告一個 iterator 變數實在太麻煩了，真的感謝 C++ 11 發明出了 auto 這個東西…

vector 取 max 方法二 - 繞過 iterator 直接取值

我們直接將 max_element 取得的 iterator 直接取值，
(這也才是我們想要的)
就可以直接得到值了，不用另外宣告 iterator。

vector<int> dp;
int max_value = *std::max_element(dp.begin(), dp.end());
cout << max_value << endl;

Reference