kadane algo
\nclass Solution {\npublic:\n   \n    int maximumSum(vector<int>& arr) {\n        \n        int n=arr.size();\n        int sum=0;\n        vector<int> l(n,0),r(
```\nclass Solution {\npublic:\n   \n    int maximumSum(vector<int>& arr) {\n        \n        int n=arr.size();\n        int sum=0;\n        vector<int> l(n,0),r(n,0);\n         int ans=INT_MIN;\n        for(int i=0;i<arr.size();i++){\n            \n            sum=sum+arr[i];  ans=max(ans,sum);\n            \n            l[i]=sum;\n            if(sum<0) sum=0;\n           \n        }\n        sum=0;\n         for(int i=arr.size()-1;i>=0;i--){\n            sum=sum+arr[i];   ans=max(ans,sum);\n           \n            r[i]=sum;\n              if(sum<0) sum=0;\n             \n        }\n       \n        for(int i=1;i<arr.size()-1;i++){\n            ans=max(ans,max(l[i-1]+r[i+1],l[i-1]+r[i+1]+arr[i]));\n        }\n        return ans;\n        \n    }\n    \n    \n};\n```
[]