O(n log^2 n) solution using Segment Tree + BS
Intuition\nhttps://leetcode.com/problems/find-maximum-non-decreasing-array-length/solutions/4329598/o-n-solution-with-detailed-explanation/\n\nTo reiterate the 
# Intuition\nhttps://leetcode.com/problems/find-maximum-non-decreasing-array-length/solutions/4329598/o-n-solution-with-detailed-explanation/\n\nTo reiterate the important parts (read the explanation above for more details)\n$\\large \\text{dp}[i] = 1 + \\max(\\text{dp}[j])$\ngiven that $\\Large \\sum\\limits_{k=j+1}^i a_k \\geqslant \\text{last}[j] \\implies \\text{psum}[i] \\geqslant\\text{psum[j]} + \\text{last}[j]$\nand we take the largest $j$ since $\\text{dp}$ is mono-increasing.\n\nThen, define an array $\\large \\text{aux}[i] = \\text{psum}[i] + \\text{last}[i]$ and make a **min** Segtree based on that. Then, at each $i$, do a binary search to find the maximum $j$ s.t. $\\text{aux}[j] \\leqslant \\text{psum}[i]$.\n\nWe know that if $\\color{5AFFA0} \\Large \\min\\limits_{k=m}^{i-1} \\: \\large \\text{aux}[k] \\leqslant \\text{psum}[i]$, then there exists at least one index \n$\\large \\color{5aa0ff} c \\in [m,i)$ such that $\\large \\color{5aa0ff} \\text{aux}[c] \\leqslant \\text{psum}[i]$, and so we can just do $\\large l := m$\n\nIf $\\color{5AFFA0} \\Large \\min\\limits_{k=m}^{i-1} \\: \\large \\text{aux}[k] > \\text{psum}[i]$, then every element $\\large \\color{5aa0ff} \\in [m,i)$ will be $\\large  \\color{5aa0ff} > \\text{psum}[i]$, so we don\'t consider that half and just do $\\large r := m-1$\n\n# Complexity\n- Time complexity:\n$\\Large \\color{pink} O(n \\log^2 n)$ since Segtree is n log n and BS is log n\n\n- Space complexity:\n$\\Large \\color{cyan} O(n)$\n\n# Code\n```\nconst long long INF = LONG_LONG_MAX - 1;\n\nclass Solution {\npublic:\ntemplate <class T> class Segtree {\n\nprivate:\n\n    const T DEFAULT = INF/2;  // Will overflow if T is an int\n\n\n    vector<T> segtree;\n\n    int len;\n\n\npublic:\n\n    Segtree(int len) : len(len), segtree(len * 2, DEFAULT) {}\n\n\n    /** Sets the value at ind to val. */\n\n    void set(int ind, T val) {\n\n        ind += len;\n\n        segtree[ind] = val;\n\n        for (; ind > 1; ind /= 2) {\n\n            segtree[ind / 2] = std::min(segtree[ind], segtree[ind ^ 1]);\n\n        }\n\n    }\n\n\n    /** @return the minimum element in the range [start, end) */\n\n    T rmin(int start, int end) {\n\n        T sum = DEFAULT;\n\n        for (start += len, end += len; start < end; start /= 2, end /= 2) {\n\n            if (start % 2 == 1) { sum = std::min(sum, segtree[start++]); }\n\n            if (end % 2 == 1) { sum = std::min(sum, segtree[--end]); }\n\n        }\n\n        return sum;\n\n    }\n\n};\n\n    long long psum[(int) 1e5 + 3];\n    int last[(int) 1e5 + 3];\n    int dp[(int) 1e5 + 3];\n\n    int findMaximumLength(vector<int>& a) {\n        int n = a.size();\n        Segtree<long long> aux(n+1);\n        psum[0] = 0;\n        for (int i = 0; i < n; ++i){\n            psum[i+1] = psum[i] + a[i];\n            aux.set(i+1,INF/2);\n        }\n\n        last[0] = 0;\n        dp[0] = 0;\n        aux.set(0,0);\n\n        for (int i = 1; i <= n; ++i){\n            // find largest j < i s.t. last[j] + psum[j] <= psum[i]\n            // C >= last[j] + psum[j]\n            // C >= aux[j]\n            long long C = psum[i];\n            int l = 0;\n            int r = i-1;\n            while ((r-l) > 1){\n                int m = (r+l)>>1;\n                if (aux.rmin(m,i) <= C)\n                    l = m;\n                else\n                    r = m-1;\n            }\n            int j = l;\n            if (aux.rmin(r,i) <= C)\n                j = r;\n\n            dp[i] = 1 + dp[j];\n            last[i] = psum[i] - psum[j];\n            aux.set(i,last[i]+psum[i]);\n        }\n        return dp[n];\n    }\n};\n```
['Binary Search', 'Dynamic Programming', 'Segment Tree', 'Prefix Sum', 'C++']