Last Updated: 23 Dec, 2021

Buying Stocks

Easy

Asked in company

Solve now

Problem statement

You have made a New Year’s Resolution to make a lot of money, and based on the advice of your smart (Not really) friends, you decide to invest in the stock market.

There are ‘N’ different stocks currently available in the market, and you have a magical machine that can accurately predict how much profit you can make on each stock. Sometimes, this value can be negative, indicating that buying it leads to a loss.

You can purchase at most ‘K’ of these stocks (or none at all). Given an array of the profits on each stock, find the maximum profit you can make.

For example:

If there are 3 stocks and the profit on them is [1,3,-2], and you are allowed to buy at most 1 stock, you can buy the second one and make a profit of 3.

Input Format:

The first line contains 'T', denoting the number of test cases.
For each Test :
The first line contains two space-separated integers, ‘N’ and ‘K’.
The second line contains ‘N’ integers, with the ith of them representing how much returns you get on the ith stock.

Output Format:

For each case, print one integer, the maximum profit you can make.

Note:

You are not required to print the expected output. It has already been taken care of. Just implement the function.

Constraints -

1 <= 'T' <= 10
1 <= ’K’ <= 'N' <= 10^5
-10^4 <= A[i] <= 10^4, i ∈ (1,N) 
Note - The sum of 'N' over all test cases does not exceed 10^5.
Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach: We can recursively generate all possible K-tuples from the ‘N’ profits, and for each K-tuple, we can take the sum of all positive profits and that will be the answer for our current tuple. The maximum of all such answers will be the final answer.

Algorithm:

Initialize ans=0
Generate all subsets of the array using bitmasking.
If the size of the current subset is not 'K'
Continue with next iteration.
Initialize temp=0
For element ele in the ‘K’ elements
If ele>0
Add ele to temp
If temp > ans
Assign ans = temp
Return ans

Solve now

02 Approach

Approach:

Each time, we can greedily try and pick the stock that gives us the largest profit. For this, we can sort the array of profits in descending order and start picking.

We can pick the ‘K’ largest profits to maximize our overall profit. However, there might be a chance that some of the ‘K’ largest stocks give negative profits, i.e loss. In that case, we only pick all the positive profits from the ‘K’ largest ones.

Algorithm:

Initialize ans=0
Sort the profit array in descending order
Initialize i = 0
While i < K
- If a[i] <= 0
  - Break
- Add a[i] to ans
- Increment i by 1
Return ans

Solve now

Buying Stocks

Problem statement

You have made a New Year’s Resolution to make a lot of money, and based on the advice of your smart (Not really) friends, you decide to invest in the stock market.

There are ‘N’ different stocks currently available in the market, and you have a magical machine that can accurately predict how much profit you can make on each stock. Sometimes, this value can be negative, indicating that buying it leads to a loss.

You can purchase at most ‘K’ of these stocks (or none at all). Given an array of the profits on each stock, find the maximum profit you can make.

For example:

Input Format:

Output Format:

Note:

Constraints -

Approaches

01 Approach

Approach: We can recursively generate all possible K-tuples from the ‘N’ profits, and for each K-tuple, we can take the sum of all positive profits and that will be the answer for our current tuple. The maximum of all such answers will be the final answer. Algorithm:

02 Approach

Approach:

Algorithm:

Approach: We can recursively generate all possible K-tuples from the ‘N’ profits, and for each K-tuple, we can take the sum of all positive profits and that will be the answer for our current tuple. The maximum of all such answers will be the final answer.

Algorithm: