100% Time and 100% Memory best DP Solution
\nclass Solution {\n    public int maximumSum(int[] arr) {\n        if(arr.length==1)\n        return arr[0];\n        int p=0,max=-1;\n        int[] dp1=new in
```\nclass Solution {\n    public int maximumSum(int[] arr) {\n        if(arr.length==1)\n        return arr[0];\n        int p=0,max=-1;\n        int[] dp1=new int[arr.length];\n        int[] dp2=new int[arr.length];\n        dp1[0]=arr[0];\n        dp2[arr.length-1]=arr[arr.length-1];\n        for (int j = 1; j < arr.length; j++) {\n            dp1[j]=Math.max(dp1[j-1]+arr[j],arr[j]);\n        }\n        for (int j = arr.length-2; j >=0; j--) {\n            dp2[j]=Math.max(dp2[j+1]+arr[j],arr[j]);\n        }\n        for(int i=0;i<arr.length;i++)\n        {\n            if(i==0)\n                max=Math.max(max,Math.max(arr[i],Math.max(dp2[i+1],arr[i]+dp2[i+1])));\n            else if(i==arr.length-1)\n                max=Math.max(max,Math.max(arr[i],Math.max(dp1[i-1],arr[i]+dp1[i-1])));\n            else\n                max=Math.max(max,Math.max(arr[i],Math.max(dp1[i-1],Math.max(dp2[i+1],Math.max(dp1[i-1]+arr[i],Math.max(arr[i]+dp2[i+1],Math.max(dp1[i-1]+dp2[i+1],dp1[i-1]+arr[i]+dp2[i+1])))))));\n        }\n        return (max);\n    }\n}\n```
['Dynamic Programming', 'Java']