Last Updated: 17 Aug, 2021
Transactions
Easy
Asked in company
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.
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
Approaches
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’.
One observation is that if we have already calculated the sum of transactions from 0 to i, let’s say p, and then while calculating the sum of transactions from 0 to i + 1, it is just p + money[i + 1]. Hence, we can store the previous sum to calculate the following answer.
The steps are as follows:
- We initialize ‘maximumMoney’ as 0.
- We initialize ‘previous’ as 0, denoting the sum of transactions till i - 1.
- Traverse the array from i = 0 to i = ‘N’ - 1.
- Update previous = previous + money[i].
- If ‘previous’ is greater than ‘maximumMoney’, update ‘maximumMoney’.
- Return ‘maximumMoney’.