C++ O(n) with clear explanation
\nclass Solution {\npublic:\n    int maximumSum(vector<int>& arr) {\n        int n = arr.size();\n        vector<pair<int,int> > dp(n);\n        dp[0] = {arr[0]
```\nclass Solution {\npublic:\n    int maximumSum(vector<int>& arr) {\n        int n = arr.size();\n        vector<pair<int,int> > dp(n);\n        dp[0] = {arr[0],arr[0]};\n        int ans = dp[0].first;\n        for(int i=1; i<n; ++i) {\n            dp[i].first = max(dp[i-1].first+arr[i], arr[i]);\n            dp[i].second = max(dp[i-1].second+arr[i],dp[i-1].first);\n            ans = max(ans,dp[i].first,dp[i].second);\n        }\n        \n        return ans;\n    }\n};\n```\n\nThe idea is that at each step we find the answers if no exclusions happen and if one exclusion happens. The following are the relations for each case:-\n1) No exclusion: This is the first value in each element of our DP table. ```dp[i].first = max(dp[i-1].first+arr[i], arr[i])``` , ie we can either start a new subarray at this point or continue the subarray from the previous element. Note that since for this case exclusions are not allowed so for ```dp[i-1]``` we are considering the first value only,\n2) Exclusion: In this case there are two sub-cases-\n\t\t\t\t\ta) We exclude current element.\n\t\t\t\t\tb) Some element has already been excluded previously.\nTherefore the relation becomes ```dp[i].second = max(dp[i-1].first, dp[i-1].second+arr[i])```. Note that in the first case if we exclude this element then the for the previous sub problem we can\'t make any exclusions therefore ```dp[i-1].first``` is considered.
[]