C++ DP solution with O(n) time and O(n) space
\npublic:\n    int maximumSum(vector<int>& arr) {\n        int ret = arr[0];\n        int skip = 0;\n        int nonskip = arr[0];\n        for (int i = 1; i < 
```\npublic:\n    int maximumSum(vector<int>& arr) {\n        int ret = arr[0];\n        int skip = 0;\n        int nonskip = arr[0];\n        for (int i = 1; i < arr.size(); i++) {\n            int tmp = nonskip;\n            nonskip = max(0, nonskip) + arr[i];\n            skip = max(tmp , skip + arr[i]);\n            ret = max({ret, nonskip, skip});\n        }\n        return ret;\n    }\n};\n```\nQuite simple idea. We keep tracing two value when traversing: one is the maximum sum that we never skip any value from the begining of the subarray to current index, one is the maximum sum that we must skip a value. When it comes to the next one, the "nonskip" sum should be the maximum of 0 and former "nonskip" sum, then plus current value, and the "skip" sum should be the maximum of previous  "nonskip" sum and previous "skip" sum plus current -- the is the maximum if we skip current, the second is the sum if we don\'t skip current.
[]