Festival K Stages Problem

Festival K Stages Problem — ExecCode Hard DSA Practice

Solve the Festival K Stages problem on ExecCode. Free online hard DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A street of stalls has profits (some negative). You may open exactly k non-overlapping contiguous stages and take the sum of those stalls. Empty gaps between stages are allowed. Partition DP (and Aliens trick when k is huge and the cost is concave) finds the maximum. Return the maximum sum of exactly k non-overlapping contiguous subarrays. Subarrays must be non-empty. If k is 0 or the array is empty, return 0. You are given: arr — stall profits k — number of stages Return maximum combined profit. A negative stall can still sit inside a stage if neighbors compensate, but you may also skip it in a gap.

Examples

Input {'arr': [1, 2, 3], 'k': 1}; Output 6. Input {'arr': [1, -5, 4], 'k': 2}; Output 5. Input {'arr': [-2, -3], 'k': 1}; Output -2

Constraints

Segments do not overlap Order along the street is fixed

Practice Festival K Stages free on ExecCode. Browse DSA problems, topic map, and placement guides.