Marisa has n flower pots arranged consecutively. Planting flowers in the i-th pot costs ai. Marisa has a budget of t, so she cannot plant flowers in all pots. The βuglinessβ of the flower pots is defined as the length of the longest contiguous segment of pots without flowers. Help Marisa find a way to plant flowers such that the ugliness is minimized while staying within the budget.
Input:
17 11
6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5
Output:
3
Explanation:
a | 6 | 4 | 5 | 2 | 5 | 3 | 4 | 5 | 2 | 3 | 4 | 5 | 2 | 3 | 6 | 3 | 5 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Plant? | β | β | β | β |
Nearest position | |
Subarray minimum | |
Peak Product | |
Histogram | |
Maximum subsequence value | |
Deleting digits | |
Electric poles | |
Planting flowers | |
Ring road | |
Prefix minimum | |
Knee surgery |