Matrix Pathways

The 'Concert Lineup' problem asks you to find the maximum enjoyment a concert promoter can get from a lineup of bands, with the constraint that no two bands of the same genre can play consecutively. It tests dynamic programming skills and optimization.

dynamic programmingoptimizationarraygreedy

Problem Statement

A music festival organizer needs to create a lineup of bands for a concert. Each band provides a certain level of enjoyment to the audience. However, to keep the audience engaged, no two bands of the same genre can play back-to-back. Given an array representing the enjoyment value of each band, determine the maximum total enjoyment the organizer can achieve by selecting a lineup that adheres to the genre constraint.

Example 1

Input: [5, 5, 10, 100, 10, 5]

Output: 110

The optimal lineup is bands with enjoyment values 5, 100, and 5, totaling 110. The two bands valued at 10 are skipped to avoid consecutive bands of the same genre.

Example 2

Input: [1, 2, 3, 1]

Output: 4

The optimal lineup is bands with enjoyment values 1 and 3, totaling 4. The two bands valued at 1 are not consecutive.

Constraints

-1 <= len(bands) <= 1000
-0 <= band_enjoyment <= 1000
-Bands are represented by an array of integers.
-The array will only contain positive integers.
-The genre of a band is represented by its enjoyment value.

Brute Force Approach

Imagine you're trying every possible combination of bands. For each combination, you'd check if any adjacent bands are of the same genre. If the combination is valid, you calculate the total enjoyment. You repeat this for every combination, keeping track of the maximum enjoyment found so far. This is like trying every single route on a map to find the shortest one - very time-consuming!

TimeO(2^n)

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem