Search with priority queue and simple heuristics
Run the largest tests under the second\n\n# Intuition\n\nA node : a partial solution with the values grouped up til an index (i_start). The first i_start values
Run the largest tests under the second\n\n# Intuition\n\n**A node** : a partial solution with the values grouped up til an index (`i_start`). The first `i_start` values form `length` sums, the last (largest) sum is of value `v_min`.\n\n**Terminal node** : when `i_start = n`\n\n**Expand** : Let `i` be the first index that `sum(nums[i_start..i]) >= v_min`. The next nodes would be: `sum(nums[i_start..i])`, `sum(nums[i_start..(i+1)])`, and so on. The search space grows exponentially.\n\n**Heuristic to reduce search space**:\n`potential of a node = (number of groups up til the node) + sum (remaining numbers) / v_min`\nIt gives the upper bound of the solutions that can be found from that node.\nSo if `(potential of a node) <= (best solution found so far)`, that node is not worth exploring. (At best, this node leads to the same number and improve nothing)\n\n**Priority queue** : We explore high `potential` nodes first.\n\n\n# Complexity\n- Time complexity: ???\n\n- Space complexity: O(N)\n\n# Code\n```\nuse std::collections::BinaryHeap;\n\n#[derive(PartialEq, Eq, PartialOrd, Ord)]\nstruct Node {\n    potential: i32,\n    i_start: usize,\n    length: i32,\n    v_min: i64,\n}\n\nimpl Solution {\n    pub fn find_maximum_length(nums: Vec<i32>) -> i32 {\n        let n = nums.len();\n        let cumsums = Self::to_cumsum(&nums);\n\n        let mut iter = 0;\n        let mut best = Self::greedy(&cumsums, 0);\n        let mut visited = vec![None; n];\n        let mut queue = BinaryHeap::with_capacity(n * 3 / 2);\n        queue.push(Node {\n            potential: i32::MAX,\n            i_start: 0,\n            length: 0,\n            v_min: 1,\n        });\n\n        // Whether a node is worth exploring\n        let is_userfull = |x: &Node, eq_ok: bool, visited: &[_], best: i32| {\n            if x.potential <= best {\n                return false;\n            }\n\n            if let Some((l1, v1)) = visited[x.i_start] {\n                if (v1 < x.v_min && l1 >= x.length) || (v1 == x.v_min && l1 > x.length) {\n                    // There is a better node in the queue\n                    return false;\n                }\n                if v1 == x.v_min && l1 == x.length {\n                    return eq_ok;\n                }\n            }\n            return true;\n        };\n\n        // Priority queue. Process first: high potential - high i_start (potential estimation is more fiable)\n        while let Some(node) = queue.pop() {\n            if !is_userfull(&node, true, &visited, best) {\n                continue;\n            }\n\n            iter += 1;\n            if iter % 1000 == 0 {\n                queue.retain(|x| is_userfull(x, true, &visited, best));\n            }\n\n            let v_prev = if node.i_start > 0 {\n                cumsums[node.i_start - 1]\n            } else {\n                0\n            };\n            for (i, &x) in cumsums[node.i_start..].iter().enumerate() {\n                let i = node.i_start + i;\n                let mut v = x - v_prev;\n                if v >= node.v_min {\n                    if i < n - 1 {\n                        let potential =\n                            node.length + 1 + ((cumsums[n - 1] - cumsums[i]) / v) as i32;\n                        let new_node = Node {\n                            potential,\n                            i_start: i + 1,\n                            length: node.length + 1,\n                            v_min: v,\n                        };\n                        if !is_userfull(&new_node, false, &visited, best) {\n                            break;\n                        }\n\n                        queue.push(new_node);\n                        visited[i + 1] = Some((node.length + 1, v));\n                    } else if node.length + 1 > best {\n                        best = node.length + 1;\n                        queue.retain(|x| x.potential > best);\n                    }\n                }\n            }\n        }\n        best\n    }\n\n    fn greedy(cumsums: &[i64], min: i64) -> i32 {\n        let mut min = min;\n        let mut count: i32 = 0;\n        let mut prev = 0;\n        for &s in cumsums {\n            let v = s - prev;\n            if v >= min {\n                min = v;\n                prev = s;\n                count += 1;\n            }\n        }\n        count\n    }\n\n    fn to_cumsum(nums: &[i32]) -> Vec<i64> {\n        let mut sum: i64 = 0;\n        let mut cumsums = Vec::with_capacity(nums.len());\n        for &x in nums {\n            sum += (x as i64);\n            cumsums.push(sum);\n        }\n        return cumsums;\n    }\n}\n```
['Rust']