Transactions

Easy

0/40

Average time to solve is 15m

Contributed by

6 upvotes

Asked in company

Problem statement

Alex is going to some stores where he will carry out some transactions. In each store, he will either pay some money, or he will receive some money. Initially, Alex has 0 amount with him. So he currently has an array 'money' containing the transaction amounts (both positive and negative) in the same order he did at stores. Can you find out the maximum amount that he will have with him after any(possibly 0) number of transactions?

Note: that at some point, the amount left with Alex can become negative. For example, in the transactions [1, -3], after the second transaction, the money left with Alex is -2.

Example: Let the transaction amounts be [1, -2, 5]. Here we can see that the amount left after the first transaction is 1 after the second is -1 and after the third is 4. So the maximum value is 4.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains ‘T’, denoting the number of test cases.

The first line of each test case contains one integer, ‘N’, denoting the number of stores.

The second line of each test case contains an array ‘money’ of ‘N’ space-separated integers, denoting the transaction amount carried out. If money[i] < 0, it means that Alex will pay |money[i]|, and if money[i] > 0, it means Alex will receive money[i] amount.

Output Format:

For each test case, print an integer denoting the maximum amount that Alex can have at any point.

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 <= N <= 10^4
-10^5 <= money[i] <= 10^5

Time Limit: 1 sec

Sample Input 1:

2
6
1 -3 5 -6 4 -3
1
11

Sample Output 1:

3
11

Explanation for Sample Input 1:

In the first test case, the transaction values are [1, -3, 5, -6, 4, -3]. We can see that after the first transaction, the money left with Alex is 1. After the second, it is -2, then 3, then -3, then 1, and finally -2. We can see that after the third transaction, the money left with Alex is 3, which is the maximum money that he can have.
In the second test case, there is only one transaction. He receives 11 in the first transaction, which is also the highest that he can have.

Sample Input 2:

2
5
5 7 11 3 5
3
-20 -19 -21

Sample Output 2:

31
0

Hint 1

Hint 2

After each transaction, can you find the money left?

Approaches (2)

Approach 1

Approach 2

Brute force

For each transaction, ‘i’ find the sum of all transactions ‘j’ such that j <= i. Update the maximum value as needed

The steps are as follows:

Initialize ‘maximumMoney’ as 0.
Traverse the array from i = 0 to i = N - 1.
- Initialize ‘currSum’ = 0
- Traverse the array from j = 0 to j = i.
  - Add ‘money[j]’ to ‘currSum’ to contain the sum of transactions from transaction 0 to transaction i.
- If the sum of transactions is more than ‘maximumMoney’, update ‘maximumMoney’.
Return ‘maximumMoney’.

Time Complexity

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

For each transaction ‘i’ we are calculating the sum of transactions from j = 0 to j = i. Hence, the overall time complexity becomes O(N ^ 2).

Space Complexity

O(1)

We are using constant space.

(100% EXP penalty)

Transactions

Console