Proof for Lee215's solution
Intuition from lee215\'s solution\n1. Doing all the negative transactions before all the positive transaction will be the worst case.\n2. The worst-case and hen
# Intuition from lee215\'s [solution](https://leetcode.com/problems/minimum-money-required-before-transactions/solutions/2588034/JavaC++Python-Easy-and-Coincise/)\n1. Doing all the negative transactions before all the positive transaction will be the worst case.\n2. The worst-case and hence the final answer depends only on the last negative transaction and the first positive transaction.\n3. In the worst-case permutations:\nLet `m` be the index of the negative transaction with maximum cashback and `l` be the index of the positive transaction with the highest cost.\nTemplate of the worst-case permuation = `[...all negative transactions in any order..., transaction[m], transaction[l], ...all psoitive transactions in any order...]`\n# To Prove\n1. `Min. starting money needed = total negative loss + max(max cashback in all negative transactions, max cost in all positive transactions)`\n`= (total negative loss) + max(B[m], A[l])`\n\n# Proof:\nLet `money_m` be the money needed to complete transaction `m` in worst case, then `money_m >= (total negative loss) + B[m]`.\n\n For any intermediate negative transaction `i` in any permutation including the worst case scenario. \n`(total negative loss) + (max cashback in all negative transactions)`\n `= (negative loss for [0, i-1]) + A[i] + (negative loss for [i+1, m] + (B[m] - B[i])` \n`>= A[i]` proving that the `money >= A[i]` invariant is satisfied for every negative transaction.\n\n\nLet `money_n` be the money needed to complete transaction `n` in worst case, then `money_n - (total negative loss) >= A[l] `\nimplies `money_n => (total negative loss) + A[l]`.\n\nJust like above we can prove that for any positive transaction i in any permutation, the invariant `money >= A[i]` will be satisfied.\n\nMin. money required = `max(money_n, money_m) = max((total negative loss) + B[m], (total negative loss) + A[l]) = (total negative loss) + max(B[m], A[l])`.\n\n\n\n# Code\n```\nclass Solution {\npublic:\n    long long minimumMoney(vector<vector<int>>& transactions) {\n        long ans = 0, totalLoss = 0, maxCashback = 0, maxCost = 0;\n        for (auto &v: transactions) {\n            if (v[0] > v[1]) {\n                totalLoss += v[0] - v[1];\n                maxCashback = max(maxCashback, (long)v[1]);\n            } else {\n                maxCost = max(maxCost, (long)v[0]);\n            }\n        }\n        return totalLoss + max(maxCost, maxCashback);\n    }\n};\n```
['C++']