[Scala] DP + Binary Search
Creds to https://leetcode.com/problems/find-maximum-non-decreasing-array-length/solutions/4329014/python-dp-binary-search/\n\n# Complexity\n- Time complexity: O
Creds to https://leetcode.com/problems/find-maximum-non-decreasing-array-length/solutions/4329014/python-dp-binary-search/\n\n# Complexity\n- Time complexity: `O(nlogn)`\n- Space complexity: `O(n)`\n\n# Code\n```\n  \n  object Solution {\n\n    import scala.collection.mutable.ArrayBuffer\n    import scala.collection.Searching.{Found, InsertionPoint}\n\n    def bisectLeft(a: Array[Long], key: Long): Int = {\n      var id = a.search(key) match {\n        case Found(idx) => idx\n        case InsertionPoint(insertionPoint) => insertionPoint\n      }\n      while (id > 0 && a(id - 1) >= key) id -= 1\n      id\n    }\n\n    def findMaximumLength(nums: Array[Int]): Int = {\n      val n = nums.length\n      val acc: Array[Long] = nums.scanLeft(0L)(_ + _)\n      val pre = ArrayBuffer.fill(n + 2)(0)\n      val dp = ArrayBuffer.fill(n + 1)(0)\n      var i: Int = 0\n      for ((a, j) <- nums zip LazyList.iterate(1)(_ + 1)) {\n        i = i max pre(j)\n        dp(j) = dp(i) + 1\n        val k = bisectLeft(acc, acc(j) * 2 - acc(i))\n        pre(k) = j\n      }\n      dp(n)\n    }\n  }\n\n```
['Scala']