Buying Stocks

Easy
0/40
Average time to solve is 10m
profile
Contributed by
11 upvotes
Asked in company
Quest Global Pvt. Services Ltd

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.
Detailed explanation ( Input/output format, Notes, Images )
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

Sample Input 1:

2
4 2
1 4 -5 3
3 3
-1 -2 -3
Sample Output 1
7
0
Explanation for Sample Input 1:
For test case 1:
You can buy the second and fourth stock and make a profit of 4+3=7.

For test case 2:
Since all stocks lead to loss, you don’t buy anything and end up with a profit of 0.
Sample Input 2:
2
5 2
1 2 3 4 100
4 3
1 3 2 -4
Sample Output 2:
104
6
Hint

In how many ways can we pick ‘K’ elements from ‘N’?

Approaches (2)
Brute Force

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
Time Complexity

O(N*(2^N)), where ‘N’ is the number of stocks.

We generate all subsets of size N, so in the worst case, we would have generated 2^N subsets, and we take linear time to process each of the subsets, so the final complexity will be O(N*(2^N)).

Space Complexity

O(1), as we use a constant amount of additional space.

Code Solution
(100% EXP penalty)
Buying Stocks
Full screen
Console