Optimal Product Curation
Nykaa's product curation team aims to optimize the display of a linear sequence of products to maximize customer engagement. Each product offers a certain "satisfaction value". To maintain variety and prevent user fatigue, specific rules dictate how many products must be skipped between any two consecutively chosen products. Your task is to implement an algorithm that finds the maximum total satisfaction value achievable under these constraints.
Implement a function maxCuratedSatisfaction that calculates the maximum total satisfaction value from selecting products based on the given rules. The function must adhere to the following:
i and then product j (where j > i), you must skip at least minSkip products and at most maxSkip products between them. That is, minSkip <= (j - i - 1) <= maxSkip.0.satisfactionScores: An array of non-negative integers (number[]), where satisfactionScores[k] represents the satisfaction value of the k-th product.minSkip: A non-negative integer (number) representing the minimum number of products to skip between two selected products.maxSkip: A non-negative integer (number) representing the maximum number of products to skip between two selected products.number) representing the maximum total satisfaction value that can be achieved.satisfactionScores is empty, the result is 0.satisfactionScores[i] >= 0, but dp[j] could be negative if satisfactionScores[j] were allowed to be negative in general DP problems), the function should return 0 (by choosing no products). However, for this problem, satisfactionScores[i] are guaranteed to be non-negative, so dp[i] values will also be non-negative.Examples
Example 1
Input:
satisfactionScores = [10, -5, 20, 3, 15], minSkip = 1, maxSkip = 2
Output:
45
Note:
Let N be the length of satisfactionScores. dp[i] represents the maximum satisfaction ending with product i. The predecessor j for product i must satisfy i - maxSkip - 1 <= j <= i - minSkip - 1.
dp[0] = 10dp[1] = -5 + max(0, dp[0]) = 5 (no valid predecessor j in range [-2, -1], so consider starting new chain at dp[0])dp[2] = 20 + max(0, dp[0]) = 30 (predecessor j in range [-1, 0], so dp[0] is considered)dp[3] = 3 + max(0, dp[0], dp[1]) = 13 (predecessor j in range [0, 1], so dp[0] and dp[1] are considered)dp[4] = 15 + max(0, dp[1], dp[2]) = 45 (predecessor j in range [1, 2], so dp[1] and dp[2] are considered)
The maximum value in dp is 45. The optimal sequence is choosing product 0 (score 10), then product 2 (score 20, skipping 1 product), then product 4 (score 15, skipping 1 product). Total: 10 + 20 + 15 = 45.Example 2
Input:
satisfactionScores = [5, 1, 10, 1, 20], minSkip = 0, maxSkip = 1
Output:
37
Note:
Here, minSkip=0 and maxSkip=1 means you can select an adjacent product (skip 0) or skip one product. This allows summing all positive values. Since all scores are positive, the optimal strategy is to pick every product if possible. The sequence 5 -> 1 -> 10 -> 1 -> 20 sums to 37. Each step skips 0 products, which is within [0,1].
Example 3
Input:
satisfactionScores = [10, 0, 0, 0, 20], minSkip = 3, maxSkip = 3
Output:
30
Note:
Here, you must skip exactly 3 products between selections. Choosing product 0 (score 10) allows the next product to be product 4 (skipping products 1, 2, 3). Choosing product 4 (score 20) leads to a total of 10 + 20 = 30. No other valid sequence yields a higher total.
Constraints
0 <= satisfactionScores.length <= 10^50 <= satisfactionScores[i] <= 10000 <= minSkip <= maxSkipsatisfactionScores.length > 0, then maxSkip < satisfactionScores.length.minSkip and maxSkip values lead to specific jump patterns (e.g., minSkip = maxSkip = 0).Loading editor...