Frontend School

Maximize Product Promotion Value

DSA
medium

Maximize Product Promotion Value

Medium
Dynamic Programming
1D DP

Overview

Flipkart is launching a new initiative to optimize product visibility and brand engagement on its platform. We're looking to strategically arrange product displays and promotional banners across a linear sequence of N available slots. The goal is to maximize the combined value generated from sales (products) and brand impact (banners).

What you need to do / Task

You are tasked with implementing a function that determines the maximum total value achievable by optimally placing products and promotional banners in a sequence of N slots.

  1. For each slot i, you must choose to either place a product or a promotional banner.
  2. If a product is placed at slot i, it generates productValues[i] in sales.
  3. If a promotional banner is placed at slot i, it generates bannerValues[i] in brand value.
  4. A critical constraint: Two promotional banners cannot be placed in consecutive slots. That is, if a banner is at slot i, slot i+1 cannot also have a banner.
  5. An additional rule: If a promotional banner is placed at slot i, it provides a fixed boostAmount to the sales value of the immediately following product (if a product is placed at slot i+1). This boost applies only once to the next product.

Input & output

Function Signature:

function maximizePromotionValue(productValues: number[], bannerValues: number[], boostAmount: number): number
  • productValues: An array of integers where productValues[i] represents the sales value generated if a product is placed in slot i.
  • bannerValues: An array of integers where bannerValues[i] represents the brand value generated if a promotional banner is placed in slot i.
  • boostAmount: A non-negative integer representing the fixed sales boost applied to the next product if a banner is placed.
  • Returns: A single integer representing the maximum total combined value (sales + brand) achievable.

Clarifications

  • The productValues and bannerValues arrays will always have the same length, representing the N slots.
  • The boostAmount is applied additively to productValues[i+1] if a banner is at i and a product is at i+1.
  • All values (productValues, bannerValues, boostAmount) are non-negative.

Examples

1

Example 1

Input:

productValues = [10, 5, 20], bannerValues = [2, 1, 3], boostAmount = 5

Output:

36

Note:

N = 3. The optimal sequence is: Product (slot 0) -> Banner (slot 1) -> Product (slot 2). This yields values: 10 (P0) + 1 (B1) + (20 + 5 boost from B1) = 10 + 1 + 25 = 36.

2

Example 2

Input:

productValues = [1, 10, 1], bannerValues = [100, 1, 100], boostAmount = 0

Output:

210

Note:

N = 3. The optimal sequence is: Banner (slot 0) -> Product (slot 1) -> Banner (slot 2). This yields values: 100 (B0) + 10 (P1) + 100 (B2) = 210. (No boost as boostAmount is 0).

3

Example 3

Input:

productValues = [50, 10, 20, 30], bannerValues = [5, 1, 2, 3], boostAmount = 10

Output:

111

Note:

N = 4. The optimal sequence is: Product (slot 0) -> Banner (slot 1) -> Product (slot 2) -> Product (slot 3). This yields values: 50 (P0) + 1 (B1) + (20 + 10 boost from B1) + 30 (P3) = 50 + 1 + 30 + 30 = 111.

Constraints

Constraints & assumptions

  • 1 <= N <= 10^5 (where N is the length of productValues and bannerValues)
  • 0 <= productValues[i] <= 1000
  • 0 <= bannerValues[i] <= 1000
  • 0 <= boostAmount <= 500
  • The total sum of values might exceed standard 32-bit integer limits, so use a data type that can handle larger sums (e.g., JavaScript's number type handles large integers up to 2^53 - 1 safely).

What interviewers evaluate

  • Correctness and Optimality: The solution correctly calculates the maximum possible value and is optimally efficient in terms of time and space complexity.
  • Dynamic Programming Approach: Demonstrates a clear understanding and application of dynamic programming principles, correctly identifying states and transitions.
  • Code Quality: Produces clean, readable, and well-structured code with appropriate variable names and comments where necessary.
  • Edge Case Handling: Correctly handles edge cases, such as N=1 and scenarios where boostAmount is zero.

Loading editor...