演算法作業 13

第1題: leetcode 300 延伸

• 該題求最長遞增子序列(Longest Increasing Subsequence)的長度。
• 請仿照影片使用dp求解

題目：[4,9,2,8,7,1,4,10,3,7]，求其最長遞增子序列(Longest Increasing Subsequence)的長度。

過程

結果

第2題: leetcode 376 延伸

• 請仿照影片使用dp求解

題目：[4,9,2,8,7,1,4,10,3,7]，求其最長擺盪(wiggle)子序列的長度。

過程

結果

第3題: leetcode 53 延伸

• 請仿照影片使用dp求解

題目：[4,-9,2,8,-7,1,4,-10,3,7]，求總和最大的連續子序列(Maximum Subarray)之和。

過程

結果

第4題: 乘積最大的連續子序列

解題思路

我一直在想怎麼寫DP
結果我後來直接放棄DP
直接刻Greedy

我的想法是
一個subarray如果是負的
那一定是正的subarray乘上負的subarray
而且這題是乘越多越好，
所以我把這題看成三個條件

• 正的subarray

  1. 那就直接紀錄這個subarray的值

• 負的subarray

  2. 去掉前面第一個負號前的所有數字
  3. 去掉後面最後一個負號後的所有數字

這三種可能性去取最大值

如果中途遇到0，就當作一個新的array重新計算

這樣的結果會是

$O(N)$

程式碼

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        long long ma=nums[0];
        long long pos=max(0,nums[0]),neg=1;
        int i=0, j=0;
        while(i<nums.size())
        {
            long long a=1,neg;
            bool flag=1;
            for(j=i;j<nums.size();j++,i++)
            {
                if(nums[j]==0)
                {
                    flag=0;
                    ma=max(ma,0LL);
                    break;
                }
                a*=nums[j];
                ma=max(ma,a);
                if(nums[j]<0)
                {
                    break;
                }
            }
            neg=min(1LL,a);
            if(flag)
            {
                a=1;
                long long tmp=1;
                for(j=j+1;j<nums.size();j++,i++)
                {
                    if(nums[j]==0)
                    {
                        ma=max(ma,0LL);
                        break;
                    }
                    a*=nums[j];
                    ma=max(ma,a);
                    if(nums[j]<0)
                    {
                        tmp=1;
                    }
                    tmp*=nums[j];
                }
                if(a<0)
                {
                    ma=max(ma,neg*a);
                }
                else
                {
                    ma=max(ma,(a/tmp)*neg);
                }
            }
            i++;
        }
        return ma;
    }
};

測試輸出輸入的畫面截圖

花費時間

44分鐘

完成程度

完全自己解出

第5題: 找零錢

解題思路

好老的梗題

假設有2塊、5塊
初始化先把所有變-1，代表不能放
再把dp[0]設為0，代表能放而且最少需要0個
接著試著放2塊，如果放2塊前是可以達成的，
那就幫他的放2塊後設成(放2塊前的數量+1)
放5塊是同樣的道理，只是過程中不斷取最小值而已(ex:10元會從5被更新成2)

程式碼

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,-1);
        dp[0]=0;
        for(auto coin:coins)
        {
            for(int i=0;i<=amount-coin;i++)
            {
                if(dp[i]!=-1)
                {
                    if(dp[i+coin]==-1)
                    {
                        dp[i+coin]=dp[i]+1;
                    }
                    else
                    {
                        dp[i+coin]=min(dp[i+coin],dp[i]+1);
                    }
                }
            }
        }
        return dp[amount];
    }
};

測試輸出輸入的畫面截圖

花費時間

7分鐘

完成程度

完全自己解出

第6題: 子集合

解題思路

簡單枚舉法
但我沒想到怎麼加速now那個vector的複製
erase也需要一點時間，也許不是最佳的方法
所以花了一點時間想
最後還是決定直接丟過去

程式碼

class Solution {
public:
    void dfs(vector<vector<int>> &ans,vector<int>& nums,vector<int> now,int x)
    {
        if(x==nums.size())
        {
            return;
        }
        dfs(ans,nums,now,x+1);
        now.push_back(nums[x]);
        ans.push_back(now);
        dfs(ans,nums,now,x+1);
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> now;
        ans.push_back(now);
        dfs(ans,nums,now,0);
        return ans;
    }
};

測試輸出輸入的畫面截圖

花費時間

10分鐘

完成程度

完全自己解出

心得

已填