class Solution {

public:

    int numWays(int n) {

        if (n == 0)

            return 1;

        vector<int> dp(n + 1, 0);

        int num = 1e9 + 7;

        dp[0] = dp[1] = 1;

        for (int i = 2; i <= n; i++) {

            dp[i] = (dp[i - 1] + dp[i - 2]) % num;

        }

        return dp[n];

    }

};

class Solution {

public:

    int maxSubArray(vector<int>& nums) {

        if (nums.size() == 1)

            return nums[0];

        vector<int> dp(nums.size(), 0);

        int res;

        res = dp[0] = nums[0];

        for (int i = 1; i < nums.size(); i++) {

            dp[i] = max(nums[i], nums[i] + dp[i-1]);

            res = max(dp[i], res);

        }

        return res;

    }

};

class Solution {

public:

    int maxSubArray(vector<int>& nums) {

        int res = nums[0];

        for(int i = 1; i < nums.size(); i++) {

            if(nums[i - 1] > 0) nums[i] += nums[i - 1];

            if(nums[i] > res) res = nums[i];

        }

        return res;  

    }

};

class Solution {

public:

    int translateNum(int num) {

        string numStr = to_string(num);

        if (numStr.length() == 1)

            return 1;

        int res = 0;

        vector<int> dp(numStr.size(), 0);

        dp[0] = 1;

        if (stoi(numStr.substr(0, 2)) <= 25)

            dp[1] = 2;

        else

            dp[1] = 1;

        for (int i = 2; i < numStr.length(); i++) {

            if (numStr[i-1] != '0' && stoi(numStr.substr(i - 1, 2)) <= 25)

                dp[i] = dp[i - 2] + dp[i - 1];

            else

                dp[i] = dp[i - 1];

        }

        return dp[numStr.size() - 1];

    }

};

class Solution {

public:

    vector<double> dicesProbability(int n) {

        vector<double> dp(6, 1.0 / 6.0);

        for (int i = 2; i <= n; i++) {

            vector<double> tmp(5 * i + 1, 0);

            for (int j = 0; j < dp.size(); j++) {

                for (int k = 0; k < 6; k++) {

                    tmp[j + k] += dp[j] / 6.0;

                }

            }

            dp = tmp;

        }

        return dp;

    }

};

class Solution {

public:

    vector<double> dicesProbability(int n) {

        vector<double> dp(6,1.0/6.0); // 这是第一轮掷骰子的结果

        for(int i=2;i<=n;i++){  // 开始计算第 2 轮至第 n 轮掷骰子的结果

            vector<double> tmp(i*5+1,0); // 初始化一个容器存储本轮的全部概率，容器大小按照 5*i+1 计算

            for(int j=0;j<dp.size();j++){ // 遍历上一轮的容器

                for(int k=j;k<j+6;k++){ // 上一轮容器的每个和值，都可对本轮的 6 个和值产生影响，位置范围为 [j,j+5]

                    tmp[k] += dp[j]/6.0; // 这里除以 6.0 的意思是，基于上一轮的和值，在本轮投出 1-6 中某个点数的概率应该是：上一轮概率 *(1/6)

                }

            }

            dp = tmp;

        }

        return dp;

    }

};

class Solution {

public:

    int maxProfit(vector<int>& prices) {

        int res = 0;

        int cur_min;

        if (prices.size() <= 1)

            return 0;

        cur_min = prices[0];

        for (int i = 1; i < prices.size(); i++) {

            if (prices[i] <= cur_min)

                cur_min = prices[i];

            else {

                res = max(res, prices[i] - cur_min);

            }

        }

        return res;

    }

};

class Solution {

public:

    int lengthOfLongestSubstring(string s) {

        if (s.length() <= 1)

            return s.length();

        map<int, set<char> > mp;

        set<char> st;

        st.insert(s[0]);

        mp[0] = st;

        int res = 1;

        for (int i = 1; i < s.length(); i++) {

            set<char> tmp = mp[i - 1];

            set<char>::iterator it = tmp.find(s[i]);

            if (it == tmp.end()) {

                // 如果没找到，则可以连续

                tmp.insert(s[i]);

                res = max(res, (int)tmp.size());

                mp[i] = tmp;

            }

            else {

                // 如果找到

                int len = tmp.size();

                for (int j = len; j >= 1; j--) {

                    char ch = s[i - j];

                    if (ch == s[i])

                        break;

                    else {

                        tmp.erase(tmp.find(ch));

                    }

                }

                mp[i] = tmp;

            }

        }

        return res;

    }

};