Efficient JS solution - DP + BS (Beat 100% both time and memory)
\n\nPro tip: Love lil Xie non-decreasingly \uD83D\uDC9C\uD83D\uDC9C\uD83D\uDC9C\n\nNote:\n- longests[i] is the longest possible non-decreasing array created usi
![image.png](https://assets.leetcode.com/users/images/777a39eb-3479-44c9-befb-0549145fe6da_1712697459.4237027.png)\n\nPro tip: Love lil Xie non-decreasingly \uD83D\uDC9C\uD83D\uDC9C\uD83D\uDC9C\n\nNote:\n- `longests[i]` is the longest possible non-decreasing array created using the first `i` elements (`i` is **not** the index of `nums`).\n- `minLasts[i]` is the minimum last element among all valid non-decreasing array of length `longests[i]`.\n- `ps` is prefix sum :)\n\n# Complexity\n- Time complexity: $$O(nlogn)$$\n- Space complexity: $$O(n)$$\n\n# Code\n```js\nlet longests = new Uint32Array(100001);\nlet minLasts = Array(100001).fill(0);\nlet ps = Array(100001).fill(0);\n\n/**\n * @param {number[]} nums\n * @return {number}\n */\nvar findMaximumLength = function (nums) {\n  let n = nums.length;\n\n  for (let i = 0; i < n; ++i) {\n    ps[i + 1] = ps[i] + nums[i];\n  }\n\n  longests.fill(1, 0, n + 1);\n  minLasts.fill(1e12, 0, n + 1);\n  minLasts[0] = 0;\n\n  for (let i = 1; i <= n; ++i) {\n    if (longests[i - 1] >= longests[i]) {\n      longests[i] = longests[i - 1];\n      minLasts[i] = Math.min(minLasts[i], minLasts[i - 1] + nums[i - 1]);\n    }\n\n    let l = i + 1;\n    let r = n;\n    let p = -1;\n\n    while (l <= r) {\n      let m = (l + r) >> 1;\n      if (ps[m] - ps[i] >= minLasts[i]) {\n        p = m;\n        r = m - 1;\n      } else {\n        l = m + 1;\n      }\n    }\n\n    if (p != -1) {\n      if (longests[i] + 1 == longests[p]) {\n        minLasts[p] = Math.min(minLasts[p], ps[p] - ps[i]);\n      } else {\n        longests[p] = longests[i] + 1;\n        minLasts[p] = ps[p] - ps[i];\n      }\n    }\n  }\n\n  return longests[n];\n};\n```
['Binary Search', 'Dynamic Programming', 'JavaScript']