Python | Binary search on monotonically increasing stack
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nFor each num at index i, we have to find j such that:\n- j < i\n- sum(N[j
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nFor each `num` at index `i`, we have to find `j` such that:\n- j < i\n- `sum(N[j+1] ... N[i]) >= H[j]`\n\nwhere:\n- `H[i] : height of nums ending at i`\n\nsum can be calculated using a prefix sum array `T`.\nEquation becomes:\n- `T[i]-T[j] >= H[j]`\n- `T[i] >= T[j]+H[j]`\n\nAfter finding the previous index `j` we can calculate height.\n- `height = T[i]-T[j]`\nand we can store `T[i]+h` in an array which can be used for finding `j` for the next iterations.\n\nThis would run in $O(n^2)$ which is not optimal. We can optimize this by storing `T[i] + H[i]` in a monotonically increasing stack and use binary search on that to find the index `j` for future iterations. This would have a time complexity of $O(n.log(n))$\n\n\n\n\n# Complexity\n- Time complexity:\n$O(n.log(n))$\n\n- Space complexity:\n$O(n)$\n\n# Code\n```\nclass Solution:\n    def findMaximumLength(self, nums: List[int]) -> int:\n        ans = 1\n        \n        T = list(accumulate(nums))\n        F = [(0, -1)]\n        D = []\n        \n        for i, t in enumerate(T):\n            j = F[bisect_right(F, (t, float(\'inf\')))-1][1]\n            if j >= 0:\n                f = t+t-T[j]\n                D.append(1 + D[j])\n            else:\n                f = t+t\n                D.append(1)\n                \n            while F and F[-1][0] >= f:\n                F.pop()\n            F.append((f, i))\n            \n        return D[-1]\n```
['Python3']