[C++] Explanation with Proof
For simplicity, I\'ll call cash as A, cashback as B\nThe i-th transaction will be (A[i], B[i])\nConsider some arbitrary order of transactions: (A[0], B[0]), (A[
For simplicity, I\'ll call cash as A, cashback as B\nThe i-th transaction will be (A[i], B[i])\nConsider some arbitrary order of transactions: (A[0], B[0]), (A[1], B[1]), ..., (A[n-1], B[n-1])\nWhat are the constrains? \n1. `Money >= A[0]`\n2. `Money - A[0] + B[0] >= A[1]`\n3. ....\n\nSo, the i-th constraint will be: \n`Money - A[0] + B[0] - A[1] + B[1] - ... - A[i-1] + B[i - 1] >= A[i]`\n`Money >= (A[0] - B[0]) + (A[1] - B[1]) + ... + (A[i-1] - B[i-1]) + A[i]`\n\nLets call `D[i] = A[i] - B[i]`\n\nSo, we have: `Money >= D[0] + .. + D[i-1] + A[i]` for all i.\n\nCombining all the constrains, we\'d have: `Money >= max_i D[0] + ... + D[i-1] + A[i]`\n\nFor every `i`, we need to find the max. value of sum of D\'s not including `i`. This can be done by picking all the D\'s that are positive(of course, if the value of D[i] > 0, don\'t forget to subtract it).\n\nHere\'s the code:\n```\nclass Solution {\npublic:\n    \n    /*\n        To complete [a_i, b_i], following needs to hold\n        \n        1. money >= a_0\n        2. money - a_0 + b_0 >= a_1\n        3. money - a_0 + b_0 - a_1 + b_1 >= a_2 ...\n        \n        money >= (a_0 + ... + a_i) - (b_0 + .. + b_(i-1)) = (a_0 - b_0) + ... + (a_(i-1) - b_(i-1)) + a_i\n        \n        money >= (d_0 + .. + d_(i-1)) + a_i\n        \n        Take max d differences and an a_i which is not in d_i\n        \n        b\'s as small as possible, a\'s as large possible\n    */\n    \n    long long minimumMoney(vector<vector<int>>& tr) {\n        int n = tr.size();\n        using ll = long long;\n        vector<ll> d(n);\n        ll pos = 0, neg = 0; \n            \n        for (int i = 0; i < n; ++i) {\n            d[i] = tr[i][0] - tr[i][1];\n            if (d[i] > 0) pos += d[i];\n        }\n        \n        ll ans = 0;\n        for (int i = 0; i < n; ++i) {\n            ll sum = pos;\n            if (d[i] > 0) sum -= d[i];\n            \n            ans = max(ans, tr[i][0] + sum);\n        }\n        \n        return ans;\n        \n        return 0;\n    }\n};\n```\n\nComments/Suggestions are welcome\n
['Greedy']