Concise Python DFS+Memo O(n) time
All DP problem can be converted to DFS+Memo. And I think the DFS way is easier to understand.\n"dfs(curIdx,canDelete)" returns the max sum ended at "curIdx", "c
All DP problem can be converted to DFS+Memo. And I think the DFS way is easier to understand.\n"dfs(curIdx,canDelete)" returns the max sum ended at "curIdx", "canDelete" indicates whether you can delete the value in "curIdx" or not.\nFor each value in "curIdx", you can choose to\n1. Add it to the previous max substring\n2. Not connect it to the previous, startup as new substring\n3. Delete it, use previous max substring if previous max substring didn\'t delete anything yet.\n\nPick up whatever makes the max value in the previous 3 conditions.\nThe @functools.lru_cache caches all input and return values. There all totally len(arr)\\*2 kinds of different inputs, so it takes O(n) time.\n\n```\nimport functools\nclass Solution:\n    def maximumSum(self, arr: List[int]) -> int:\n        @functools.lru_cache(None)\n        def dfs(curIdx,canDelete):\n            if curIdx<0:\n                return -math.inf\n            a=dfs(curIdx-1,False) if canDelete else -math.inf\n            b=dfs(curIdx-1,canDelete)+arr[curIdx]\n            return max(a,b,arr[curIdx])\n        return max(dfs(i,True) for i in range(len(arr)))\n```
[]