Leetcode Problem:

• Maximum Value of an Ordered Triplet I

Summary

• The problem requires finding the maximum value of a triplet of indices (i, j, k) in a given array such that i < j < k, and the value of the triplet is (nums[i] - nums[j]) * nums[k].

Approach

• The approach used is a recursive combination of elements from the array to form triplets, and the maximum value is updated accordingly.

Complexity

• O(n^3) due to the recursive combination of elements and the use of a vector to store selected elements.

Explanation

• The solution uses a recursive function combi() to generate all possible triplets of indices and calculate their values
• The function takes the current index, depth, and a vector of selected elements as parameters
• If the depth is 3, the function updates the maximum value if the current triplet has a greater value
• Otherwise, it recursively calls itself for the next index and increments the depth
• The function also uses backtracking to explore all possible combinations of elements by popping the last element from the vector and restoring the previous state.

Solution Code:

class Solution {
public:
    long long ans = 0;
    void combi(vector&nums, int cur, int depth, vector& selected){
        if(depth == 3){
            ans = max(ans, (selected[0] - selected[1])*selected[2]);
            return;
        }
        for(int i = cur + 1; i < nums.size(); i++){
            selected.push_back(nums[i]);
            combi(nums, i, depth + 1, selected);
            selected.pop_back();
        }
    }
    long long maximumTripletValue(vector& nums) {
        vector selected;
        combi(nums,-1, 0, selected);
        return ans;
    }
};

Leetcode Problem:

• Solving Questions With Brainpower

Summary

• Given a 2D array of questions where each question has a point value and a brainpower value, find the maximum points that can be earned by solving the questions in order.

Approach

• Dynamic Programming: The problem can be solved using dynamic programming
• The idea is to maintain a memoization table to store the maximum points that can be earned for each question
• The function iterates over the questions in reverse order and for each question, it calculates the maximum points that can be earned by either solving the current question or skipping it.

Complexity

• O(N) where N is the number of questions, as each question is visited once.

Solution Code:

class Solution {
public:
    long long memo[200001] = {0};
    long long mostPoints(vector>& questions) {
        int N = questions.size();
        for(int i = N - 1; i >= 0; i--){
            int point = questions[i][0];
            int brainpower = questions[i][1];
            memo[i] = max(point + memo[i + brainpower + 1], memo[i+1]);
        }
        return memo[0];
    }
};

Leetcode Problem:

• Put Marbles in Bags

Summary

• The problem requires finding the difference between the maximum and minimum scores of marble distributions given an array of weights and the number of bags.

Approach

• The solution uses a prefix sum array to efficiently calculate the sum of weights for each subarray
• It then sorts the prefix sum array and iterates through it to calculate the minimum and maximum scores by adding the weights at specific indices
• The difference between the maximum and minimum scores is then returned.

Complexity

• O(n log n) due to the sorting of the prefix sum array, where n is the number of weights.

Solution Code:

class Solution {
public:
    long long putMarbles(vector& weights, int k) {
        if(weights.size() == k) return 0;
        vector prefixSum;
        long long sum = weights[0];
        for(int i = 1 ; i < weights.size(); i++){
            sum += weights[i];
            prefixSum.push_back(sum);
            sum -= weights[i-1];
        }
        sort(prefixSum.begin(), prefixSum.end());

        long long maxScore = weights[0] + weights[weights.size() - 1];
        long long minScore = weights[0] + weights[weights.size() - 1];
        for(int i = 0; i < k - 1; i++){
            minScore += prefixSum[i];
            maxScore += prefixSum[prefixSum.size() - 1 - i];
        }

        return maxScore - minScore;
    }
};