Amazon aims to optimally package parcels to improve efficiency. There are n parcels (0-based indexing), and the price of the ith parcel is denoted by prices[i]. Amazon uses five different stamps (indexed from 1 to 5) to label the parcels.
Packaging is done sequentially from left to right, and each parcel must be labeled with one of the five stamps. A packaging is considered perfect if it adheres to the following rules (for i > 0):
prices[i] > prices[i-1], then stamp[i] > stamp[i-1] (where stamp[i] is the index of the stamp used to label the ith parcel).prices[i] < prices[i-1], then stamp[i] < stamp[i-1].prices[i] = prices[i-1], then stamp[i] ≠ stamp[i-1].
Given an array of n integers, find the number of perfect packaging possibilities using the five different stamps. Since the number of perfect packaging can be large, return the result modulo (109 + 7).
Note: If no valid packaging can be done based on the given rules, return 0.
Function Description
Complete the function getNumPerfectPackaging in the editor.
getNumPerfectPackaging has the following parameter:
int prices[n]: the price of the parcels
Returns
int: the number of perfect packaging that can be done modulo (109 + 7)
⊹ ࣪ ﹏𓊝﹏𓂁All Credit to Spike!﹏⊹ ࣪ ˖
Example 1:
Input: prices = [3, 1, 1]
Output: 40
Explanation:Here, the first parcel can be labeled with any stamp. The index of the stamp used to label the second parcel must be smaller than the one used for the first parcel. Additionally, the stamp used to label the last parcel must not be the same as the one used for the second parcel.
i.e. [3, 2, 1], [4, 2, 1], [4, 3, 2], [4, 3, 1], and so on.
Example 2:
Input: prices = [1, 2, 3]
Output: 10
Explanation:There are 10 perfect packaging combinations that can be done by labeling he parcels. For example, [1, 2, 3] means that the first parcel is labeled with the first-indexed stamp, the second parcel with the second-indexed stamp, and the third parcel with the third-indexed stamp. Hence, the ans is 10 :)
1 ≤ n ≤ 1051 ≤ prices[i] ≤ 105
input:
output: