---
# System prepended metadata

title: Problem Statement

---

# Problem Statement

Given a set of investment projects with their respective profits, we need to find the **most profitable projects**. We are given an initial capital and are allowed to invest only in a fixed number of projects. Our goal is to choose projects that give us the maximum profit.

We can start an investment project only when we have the required capital. Once a project is selected, we can assume that its profit has become our capital.

**Example 1:**

**Input:** Project Capitals=[0,1,2], Project Profits=[1,2,3], Initial Capital=1, Number of Projects=2  
**Output:** 6  
**Explanation:**

1.  With initial capital of ‘1’, we will start the second project which will give us profit of ‘2’. Once we selected our first project, our total capital will become 3 (profit + initial capital).
2.  With ‘3’ capital, we will select the third project, which will give us ‘3’ profit.

After the completion of the two projects, our total capital will be 6 (1+2+3).

**Example 2:**

**Input:** Project Capitals=[0,1,2,3], Project Profits=[1,2,3,5], Initial Capital=0, Number of Projects=3  
**Output:** 8  
**Explanation:**

1.  With ‘0’ capital, we can only select the first project, bringing out capital to 1.
2.  Next, we will select the second project, which will bring our capital to 3.
3.  Next, we will select the fourth project, giving us a profit of 5.

After selecting the three projects, our total capital will be 8 (1+2+5).


# Starting Code

```python
def find_maximum_capital(capital, profits, numberOfProjects, initialCapital):
	return  -1

def main():
	print("Maximum capital: " +
		str(find_maximum_capital([0,  1,  2],  [1,  2,  3],  2,  1)))
	print("Maximum capital: " +
		str(find_maximum_capital([0,  1,  2,  3],  [1,  2,  3,  5],  3,  0)))

main()

# Output:
# Maximum capital: 6
# Maximum capital: 8
```
---

# Zexing's Implementation

## Time Complexity: O(projects * len(capitals))

```
    for(int i = 0; i < numberOfProjects; i++){
        int maxIdx = 0;
        for(int j = 0; j < capital.length; j++){
            if(capital[j] <= initialCapital ){
                if(profits[j] > profits[maxIdx]) maxIdx = j;
            }else{
                break;
            }
        }
        initialCapital += profits[maxIdx];

    }
    return initialCapital;
    
    
    PriorityQueue<Integer> maxPq = new PriorityQueue<Integer> ((a, b) -> capital[a] - capital[b]);
    PriorityQueue<Integer> minPq = new PriorityQueue<Integer> (Collections.reverse(), (a, b) —> profits[b] - profits[a]);
    for(int i = 0; i < capital.length; i++){
        minPq.offer(i);
    }
    for(int i = 0; i < numberOfProjects; i++){
        while(!minPq.isEmpty() && minPq.peek() <= initialCapital){
            maxPq.offer(minPq.poll());
        }
        if(!maxPq.isEmpty()){
            initialCapital += maxPq.poll();
        }else{
            break;
        }
    }
    return initialCapital;


```

## Another Example

initialCapital = 1
projectCapitals = [0,1,2, 3, 5, 6 , 7]
projectProfits  = [3,2,1]

1. projectCapital[1] => profit = 1 + 2 == 3
2. projectCapital[2] => profit = 3 + 1 == 4

WHEN IT SHOULD BE

2. projectCapital[0] => profit = 3 + 3 = 6

