[Java/C++/Python] DP + Binary Search
Intuition\nAssume dp[i] is the result for i first elements.\nthe i first elements can be a non-decreasing array with length dp[i],\nafter applying operations.\n
# **Intuition**\nAssume `dp[i]` is the result for `i` first elements.\nthe `i` first elements can be a non-decreasing array with length `dp[i]`,\nafter applying operations.\n\nFor the next `A[i]`,\nwe can append it to previous last element,\nand it\'s still non-decreasing array.\nSo we prove that `dp[i] <= dp[i + 1]`,\nresult `dp` is also a non-decreasing array.\n<br>\n\n# **Intuition II**\nBecause `dp` is increasing,\nso for each `A[j]`,\nwe want to find the biggest `i` that,\n `A[i] + A[i + 1] .. + A[j]` is big enough to make the applied array non-decreasing,\nthen `dp[j + 1] = dp[i] + 1`.\n\n\n# **Solution 1**\nAfter the above intuition,\nwe can have this "brute force" solution.\n`acc` is the prefix sum array of `A`.\n\nTime `O(n^2)`, will be TLE\nSpace `O(n)`\n\n**Python**\n```py\n    def findMaximumLength(self, A: List[int]) -> int:\n        n = len(A)\n        last = [0] + [inf] * n\n        acc = [0]\n        dp = [0] + [0] * n\n        for j in range(n):\n            a = A[j]\n            acc.append(a + acc[-1])\n            i = j\n            while last[i] > acc[-1] - acc[i]:\n                i -= 1\n            last[j + 1] = acc[-1] - acc[i]\n            dp[j + 1] = dp[i] + 1\n        return dp[-1]\n```\n<br>\n\n\n\n# **Solution II**\nThe sum of last group of elements is `acc[j] - acc[i] = A[i] + ... + A[j - 1]`.\nWe will find the next shortest group starting from `A[j]`  to `A[k - 1]`\nto make it bigger than current group.\n`acc[j] - acc[i] <= acc[k] - acc[j]`\nso that `acc[j] * 2 - acc[i] <= acc[k]`.\n\nSo we can apply binary search in `acc` array,\nto find the lower bound index of `acc[j] * 2 - acc[i]`.\nAnd we assign `pre[k] = j`, which means\nto make the `k` first element non-decreasing,\nwe need to at least to sum up `A[j] + A[j + 1] + .. A[k - 1]` to make it big enough.\n<br>\n\n# **Complexity**\nTime `O(nlogn)`\nSpace `O(n)`\n<br>\n\n**Java**\n```java\n    public int findMaximumLength(int[] A) {\n        int n = A.length;\n        int[] pre = new int[n + 2], dp = new int[n + 1];\n        long[] acc = new long[n + 1];\n        for (int i = 1; i <= n; i ++) {\n            acc[i] = acc[i - 1] + A[i - 1];\n        }\n        for (int i = 0, j = 1; j <= n; j++) {\n            i = Math.max(i, pre[j]); // if this was previously optimizesd.\n            dp[j] = dp[i] + 1;\n            int k = Arrays.binarySearch(acc, 2 * acc[j] - acc[i]);\n            if (k < 0) {\n                k = -k - 1;\n            }\n            pre[k] = j;\n        }\n        return dp[n];\n    }\n```\n**C++**\nupdated from @user7634rI\n```cpp\n    int findMaximumLength(vector<int>& A) {\n        int n = A.size();\n        vector<int> pre(n + 2), dp(n + 1);\n        vector<long long> acc(n + 1);\n        for (int i = 1; i <= n; i ++) {\n            acc[i] = acc[i - 1] + A[i - 1];\n        }\n        for (int i = 0, j = 1; j <= n; j++) {\n            i = max(i, pre[j]); // if this was previously optimizesd.\n            dp[j] = dp[i] + 1;\n            int k = lower_bound(acc.begin(), acc.end(), 2 * acc[j] - acc[i]) - acc.begin();\n            pre[k] = j;\n        }\n        return dp[n];\n    }\n```\n**Python**\n```py\n    def findMaximumLength(self, A: List[int]) -> int:\n        n = len(A)\n        acc = list(accumulate(A, initial = 0))\n        pre = [0] * (n + 2)\n        dp = [0] * (n + 1)\n        i = 0\n        for j,a in enumerate(A, 1):\n            i = max(i, pre[j])\n            dp[j] = dp[i] + 1 # if this was previously optimizesd\n            k = bisect_left(acc, acc[j] * 2 - acc[i])\n            pre[k] = j\n        return dp[n]\n```\n
['C', 'Python', 'Java']