Hard

Quiz

#502 IPO

APPROACH

You are preparing for an IPO and can complete at most k projects to raise capital beforehand. Each project i requires minimum capital capital[i] and yields profit profits[i] on completion. Profits are added to your capital immediately.

Starting with capital w, choose at most k projects to maximize your final capital. Return the final maximized capital.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]

Output: 4

Explanation: Since your initial capital is 0, you can only start the project indexed 0.

After finishing it you will obtain profit 1 and your capital becomes 1.

With capital 1, you can either start the project indexed 1 or the project indexed 2.

Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.

Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

Example 2:

Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]

Output: 6

1 of 4

1:00

What is the optimal approach for this problem?