Rust solution using Prefix sum and Binary search
Work on a cumulative sequence (prefix sum) which allows the use of dichotomy in research\nFor each value in this sequence, find by dichotomy the index to the ri
Work on a cumulative sequence (prefix sum) which allows the use of dichotomy in research\nFor each value in this sequence, find by dichotomy the index to the right where the next non-decreasing value should be found,\ncalculated by the formula Prefsum[i+1] = 2*Prefsum[i] - Prefsum[i-1]\nSave this search by dichotomy at the index found with two pieces of information (tuple) 1. the incremented length counter 2. the value of the last sum Prefsum[i] (origine)\nManage two cases:\n- When you arrive at an index, use the dichotomy search result of the previous index if it is better (superior, because we want to maximise length) than that of the current index\n- When you save a search by dichotomy in an index, check that there is not already a better one\n\nex. nums = [4,3,2], prefsum = [4,7,9], lengths = [(0,0),(0,0),(0,0),(0,0)]\n\n- i=0: search 2*4 - 0 = 8, result = 2, lengths = [(0,0),(0,0),(1,4),(0,0)]\n- i=1: search 2*7 - 0 = 14, result = 3, lengths = [(0,0),(0,0),(1,4),(1,7)]\n- i=1: search 2*9 - 4 = 14, result = 3, (2,9) > (1,7) => lengths = [(0,0),(0,0),(1,4 ),(2,9)]\n\n# Code\n```\nimpl Solution {\n  pub fn find_maximum_length(nums: Vec<i32>) -> i32 {\n    let n = nums.len();\n    let mut prefsum = vec![0 as u64; n];\n    let mut lengths = vec![(0,0); n+1];\n    prefsum[0] = nums[0] as u64;\n    for i in 1..n {\n      prefsum[i] = prefsum[i-1] + nums[i] as u64;\n    }\n\n    for i in 0..n {\n      if i > 0 {\n        lengths[i] = std::cmp::max(lengths[i], lengths[i-1]);\n      }      \n      let idx = match prefsum.binary_search(&(2*prefsum[i] - lengths[i].1)) {\n        Ok(e) => e,\n        Err(e) => e,\n      };\n      lengths[idx] = std::cmp::max(lengths[idx], (lengths[i].0 + 1, prefsum[i]));\n    }\n    lengths[n].0\n  }\n}\n```
['Rust']