[Beats 100%]Very Simple C++ Solution with O(N) space
IntuitionApproachComplexity
Time complexity: O(2*M*N)

Space complexity:O(2*N)
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

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

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

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

# Code
```cpp []
class Solution {
public:
    int maximumAmount(vector<vector<int>>& coins) {
        int m = coins.size();
        int n = coins[0].size();
        vector<vector<int>> prev(3, vector<int>(n + 1, -1000000));
        vector<vector<int>> curr(3, vector<int>(n + 1, -1000000));
        for (int k = 0; k < 3; ++k) {
            prev[k][0] = 0;
            prev[k][1] = 0;
            curr[k][0] = 0;
        }


        for (int i = 1; i <= m; ++i) {
            for (int k = 0; k < 3; ++k) {
                for (int j = 1; j <= n; ++j) {
                    curr[k][j] = max(prev[k][j], curr[k][j - 1]) + coins[i - 1][j - 1];
                    if (coins[i - 1][j - 1] < 0 && k > 0) {
                        curr[k][j] = max(max(curr[k - 1][j - 1], prev[k - 1][j]), curr[k][j]);
                    }
                }
            }
            prev = curr;
            curr = vector<vector<int>>(3, vector<int>(n + 1, -1000000));
        }
        return max(prev[0].back(), max(prev[1].back(), prev[2].back()));
  }
};
```
['C++']