Lesnar001's blog

DP problem
By Lesnar001, history, 9 months ago, In English

In a day, an account holder at HackerBank wants to make n transactions. In each transaction, money is either sent (negative amount) or received (positive amount). Given n transactions, the transactions occur in order from transaction 1 through transaction n, but transactions may be skipped. The balance starts at 0 and is the running sum of the selected transactions. It can never go negative.

Find out the maximum number of transactions possible.

Example transaction = 3,2, 5,

|

One solution is to perform transactions 1, 2, 3, and 6. Transactions are 0 + 3 +2 +(-5) + 4 and balances are (3,5, 0, 4]. Return 4, the maximum number of transactions possible.

Function Description Complete the function maximizeTransactions in the editor below.

maximizeTransactions has the following parameter(s): int transaction[n]: the transaction amounts

Returns int: the maximum number of transactions possible Constraints

1 <= n <= 2000

-1e9 <= transaction[i] <= 1e9

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I believe this can be solved using a minHeap. Here's the approach:

  1. Iterate through each index of the array.
  2. Add the current element's value to a variable, which we'll call sum to keep track of the running sum.
  3. Simultaneously, insert the element into a minHeap.
  4. If, at any point, the sum becomes less than zero, keep removing the top values from the minHeap and subtract them from sum to maintain a non-negative sum.

The final answer is the size of the minHeap

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Upon thorough examination, it has come to our attention that the question in reference is identical to one present in the HackerRank library. Given the importance of maintaining integrity and originality within the programming community, I believe it is imperative to address this duplication.

As such, I kindly request your prompt attention to remove the aforementioned question from the Codeforces platform to uphold the standards of authenticity and respect for intellectual property.

Thank you for your understanding and cooperation in this matter.

Sincerely, Content Team HackerRank

→ Reply