Short and intuitive answer (Python O(n))
\n\n    def maximumSum(self, arr):\n        n = len(arr)\n        if n == 1:\n            return arr[0]\n        \n        curSumCont = 0\n        curSum = arr[
\n\n    def maximumSum(self, arr):\n        n = len(arr)\n        if n == 1:\n            return arr[0]\n        \n        curSumCont = 0\n        curSum = arr[0]\n        res = curSum\n        for i in range(1, n):\n            curSumCont = max(curSumCont + arr[i-1], arr[i-1])\n            curSum = max(curSum + arr[i], curSumCont, arr[i])\n            res = max(curSum, res)\n            \n        return res
[]