LC Weekly Contest 431

https://leetcode.com/contest/weekly-contest-431/

3411. Maximum Subarray With Equal Products

class Solution {
public:
    int maxLength(vector<int>& nums) {
        int n = nums.size();
        int ans = 1;
        for (int i = 0; i < n; i++) {
            long long total = nums[i], g = nums[i], l = nums[i];
            vector<bool> have(11, false);
            for (int j = i + 1; j < n; j++) {
                total *= nums[j];
                g = gcd(g, nums[j]);
                l = lcm(l, nums[j]);
                if (total == g * l) ans = max(ans, j - i + 1);
                else break;
            }
        }
        return ans;
    }
};

Time Complexity: O(n ^ 2)
Space: O(1)

3412. Find Mirror Score of a String

typedef long long ll;
class Solution {
public:
    long long calculateScore(string s) {
        int n = s.size();
        vector<vector<int>> cnt(26);
        ll ans = 0;
        for (int i = 0; i < n; i++) {
            int target = 25 - (s[i] - 'a');
            if (cnt[target].size()) {
                ans += i - cnt[target].back();
                cnt[target].pop_back();
            } else {
                cnt[s[i] - 'a'].push_back(i);
            }
        }
        return ans;
    }
};

Time Complexity: O(n)
Space: O(n)

3413. Maximum Coins From K Consecutive Bags

typedef long long ll;
class Solution {
public:
    long long maximumCoins(vector<vector<int>>& coins, int k) {
        sort(coins.begin(), coins.end());
        int n = coins.size();
        int l = 0, r = 0;
        int len = 0;
        ll ans = 0;
        ll cur = 0;
        while (r < n) {
            while (r < n) {
                int nxt = coins[r][1] - coins[r][0] + 1;
                int gap = 0;
                if (l != r) {
                    gap = coins[r][0] - coins[r - 1][1] - 1;
                }
                if (len + nxt + gap > k) break;
                len += nxt + gap;
                cur += 1ll * nxt * coins[r][2];
                r += 1;
            }
            ll tmp = 0;
            if (r < n) {
                int gap = r > l ? coins[r][0] - coins[r - 1][1] - 1 : 0;
                ll left = k - len - gap;
                tmp = max(1ll * 0, left * coins[r][2]);
            }
            ans = max(ans, cur + tmp);
            if (r > l) {
                len -= coins[l][1] - coins[l][0] + 1;
                cur -= 1ll * (coins[l][1] - coins[l][0] + 1) * coins[l][2];
            }
            if (l + 1 < n && l + 1 < r) {
                int gap = coins[l + 1][0] - coins[l][1] - 1;
                len -= gap;
            }
            l += 1;
            r = max(r, l);
        }

        cur = 0, len = 0;
        l = n - 1;
        r = n - 1;
        while (l >= 0) {
            while (l >= 0) {
                int nxt = coins[l][1] - coins[l][0] + 1;
                int gap = 0;
                if (l != r) {
                    gap = coins[l + 1][0] - coins[l][1] - 1;
                }
                if (len + nxt + gap > k) break;
                len += nxt + gap;
                cur += 1ll * nxt * coins[l][2];
                l -= 1;
            }
            ll tmp = 0;
            if (l >= 0) {
                int gap = r > l ? coins[l + 1][0] - coins[l][1] - 1 : 0;
                ll left = k - len - gap;
                tmp = max(1ll * 0, left * coins[l][2]);
            }
            ans = max(ans, cur + tmp);
            if (l < r) {
                len -= coins[r][1] - coins[r][0] + 1;
                cur -= 1ll * (coins[r][1] - coins[r][0] + 1) * coins[r][2];
            }
            if (r - 1 >= 0 && r - 1 > l) {
                int gap = coins[r][0] - coins[r - 1][1] - 1;
                len -= gap;
            }
            r -= 1;
            l = min(r, l);
        }
        return ans;
    }
};

Time Complexity: O(nlogn)
Space: O(1)

我們有兩種可能找到最佳，一種是從某個的頭一路過去，另一個會是從尾巴一路過去，但是他的實作沒有很好做出來就是了。