Flower Bouquet Revenue
MediumDynamic Programming · Visa
A florist has a row of flowers described by the string flowers, where "0" is a rose and "1" is a cosmos. Flowers can only be bundled with their neighbors in the row, and each flower can be used in at most one bouquet. There are two kinds of bouquets:
- Type 1: three adjacent roses (
"000"), sold forp. - Type 2: two adjacent flowers made of one rose and one cosmos (
"01"or"10"), sold forq.
Bouquets are made from consecutive flowers and must not overlap. Flowers that are not used are discarded.
Return the maximum total revenue the florist can earn.
Example 1
- Input:
- flowers = "0001000", p = 5, q = 3
- Output:
- 10
- Explanation
- Two type 1 bouquets from
000at both ends earn 5 + 5 = 10, leaving the cosmos unused. Pairing the cosmos with a neighbor would break one of the triples and earn less.
Example 2
- Input:
- flowers = "0001", p = 2, q = 3
- Output:
- 3
- Explanation
- Taking
000first earns only 2. Using the last rose and the cosmos as01earns 3, and the two remaining roses cannot form anything, so 3 is best.
Example 3
- Input:
- flowers = "0110", p = 4, q = 1
- Output:
- 2
- Explanation
- There are not three adjacent roses, so the best is the pairs
01and10for 1 + 1 = 2.
Constraints
1 <= flowers.length <= 10^5flowerscontains only"0"and"1"0 <= p, q <= 10^4