c++() forward & backward prefix sum
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
  long long maximumCoins(vector<vector<int>>& coins, int k) {
    sort(coins.begin(), coins.end());

    long ans = 0;
    int n = coins.size();
    vector<long> ps(n + 1);
    ps[0] = 0;
    for(int i = 0; i != n; ++i) 
      ps[i+1] = ps[i] + (long)coins[i][2]*(coins[i][1] - coins[i][0] + 1);

    for(int i = 0, j = 0; i != n ; ++i){
      while(j != n && coins[j][1] - coins[i][0] + 1 <= k) j++;
      long sum = ps[j] - ps[i];

      if(j != n && coins[i][0] + k > coins[j][0] ) 
        sum += (long)coins[j][2]*(coins[i][0] + k - coins[j][0]);
      
      ans = max(ans, sum);
    }

    ps[n] = 0;
    for(int i = n-1; i >= 0; --i) 
      ps[i] = ps[i+1] + (long)coins[i][2]*(coins[i][1] - coins[i][0] + 1);

    for(int i = n-1, j = n-1; i >= 0 ; --i){
      while(j != -1 && coins[i][1] - coins[j][0] + 1 <= k) j--;
      long sum = ps[j+1] - ps[i+1]; 

      if(j != -1 && coins[i][1] - k < coins[j][1] ) 
        sum += (long)coins[j][2]*(coins[j][1] - coins[i][1] + k);

      ans = max(ans, sum);
    }

    return ans;
  }
};
```
['C++']