Top Down DP
\nclass Solution {\npublic:\n    \n    int find(int i,int j,vector<int>&a,vector<vector<int> >&dp){\n        if(i==a.size())\n            return 0;\n        if(
```\nclass Solution {\npublic:\n    \n    int find(int i,int j,vector<int>&a,vector<vector<int> >&dp){\n        if(i==a.size())\n            return 0;\n        if(dp[i][j]!=-1)\n            return dp[i][j];\n        if(j==0){\n            int x=find(i+1,1,a,dp);\n            int y=a[i]+find(i+1,0,a,dp);\n            dp[i][j]=max(0,max(x,y));\n        }\n        else{\n            dp[i][j]=max(0,a[i]+find(i+1,1,a,dp));\n        }\n        return dp[i][j];\n    }\n    \n    int maximumSum(vector<int>& arr) {\n        vector<vector<int> >dp(arr.size(),vector<int>(2,-1));\n        int flag=0;\n        int maxi=INT_MIN;\n        for(int i=0;i<arr.size();i++){\n            if(arr[i]>0)\n            {\n                flag=1;\n                break;\n            }\n            maxi=max(maxi,arr[i]);\n        }\n        if(flag==0)\n            return maxi;\n        find(0,0,arr,dp);\n        int ans=0;\n        for(int i=0;i<dp.size();i++){\n            for(int j=0;j<2;j++){\n                ans=max(ans,dp[i][j]);\n            }\n        }\n        return ans;\n    }\n};\n```
[]