Java Memoization Solution in O(n) solution very easy to understand
\nclass Solution {\n    static long[][][] aa;\n    static long maxx(int[] arr,int flag1,int flag2,int ind){\n        if(ind>=arr.length && flag2==0){\n         
```\nclass Solution {\n    static long[][][] aa;\n    static long maxx(int[] arr,int flag1,int flag2,int ind){\n        if(ind>=arr.length && flag2==0){\n            return Integer.MIN_VALUE;\n        }\n        if(ind>=arr.length && flag2==2){\n            return Integer.MIN_VALUE;\n        }\n                if(ind>=arr.length && flag2==3){\n            return Integer.MIN_VALUE;\n        }\n\n        if(ind>=arr.length && flag2==1){\n            return 0;\n        }\n        if(aa[ind][flag1][flag2]!=Integer.MAX_VALUE){\n            return aa[ind][flag1][flag2];\n        }\n        if(flag1==0){\n            return aa[ind][flag1][flag2]= Math.max(maxx(arr,1,0,ind),maxx(arr,0,0,ind+1));\n        }\n        else{\n            if(flag2==0){\n                return aa[ind][flag1][flag2]=Math.max(maxx(arr,1,3,ind+1),maxx(arr,1,2,ind+1)+arr[ind]);\n            }\n                else if(flag2==3){ \n                    return aa[ind][flag1][flag2]=maxx(arr,1,1,ind+1)+arr[ind];\n                } \n            \n            else if(flag2==2){\n                return aa[ind][flag1][flag2]= Math.max(maxx(arr,1,1,ind+1),maxx(arr,1,2,ind+1)+arr[ind] );\n            }\n            else{\n                return aa[ind][flag1][flag2]= Math.max( 0,maxx(arr,1,1,ind+1)+arr[ind] );\n            }\n        }\n    }\n    \n    public int maximumSum(int[] arr) {\n        if(arr.length==1){return arr[0];}\n        aa=new long[arr.length][2][4];\n        for(int i=0;i<arr.length;i++){\n            for(int j=0;j<2;j++){\n                for(int k=0;k<4;k++){\n                    aa[i][j][k]=Integer.MAX_VALUE;\n                }\n            }\n        }\n        return (int)maxx(arr,0,0,0);\n    }\n}\n```
[]