🚀

Thanksgiving Sale: Use Coupon Code THANKS25 to Get Extra 25% Off.

00DAYS
:
00HOURS
:
00MINUTES
:
00SECONDS

Leetcode Problem 2355. Maximum Number of Books You Can Take

2355. Maximum Number of Books You Can Take

Leetcode Solutions

Dynamic Programming with Monotonic Stack

  1. Initialize an empty stack s and a DP array dp of length n (number of shelves).
  2. Iterate over each shelf index i from 0 to n - 1.
    • While the stack is not empty and the top of the stack does not maintain the monotonic property with i, pop the stack.
    • If the stack is empty, calculate dp[i] as the sum of the arithmetic progression from 0 to i.
    • Otherwise, let j be the top of the stack. Calculate dp[i] as dp[j] + calculateSum(j + 1, i).
    • Push i onto the stack.
  3. Return the maximum value in the dp array.
UML Thumbnail

Brute Force with Optimization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...