[Rust] Kadane algorithm with Explanation
\nThis is a variant of the maximum subarray problem (wikipedia), and a typical solution is Kadane\'s algorithm:\n\npython\ndef kadane(numbers):\n    """Find the
\nThis is a variant of the [maximum subarray problem (wikipedia)](https://en.wikipedia.org/wiki/Maximum_subarray_problem), and a typical solution is `Kadane\'s algorithm`:\n\n```python\ndef kadane(numbers):\n    """Find the largest sum of any contiguous subarray."""\n    best_sum = 0  # or: float(\'-inf\')\n    current_sum = 0\n    for x in numbers:\n        current_sum = max(0, current_sum + x)\n        best_sum = max(best_sum, current_sum)\n    return best_sum\n```\n\nA naive solution to our question is to loop over `arr * k`, and return the `best_sum` in the end. However, with large `k` (e.g., 100_000), we will get `Limited Time Error` (try it).\n\nLuckily, we can find patterns. To illustrate, we take `arr = [-2, 5, -1]` as an example. Observe the following facts:\n1. `sum(arr) = 2 > 0`\n2. when `k = 2`, sub-array yields the best sum is `[5, -1, -2, 5]` and its sum is `7`, \n3. when `k = 3`, sub-array yields the best sum is `[5, -1, -2, 5, -1, -2, 5]`, and its sum is `9`, \n4. when `k = 4`, sub-array yields the best sum is `[5, -1, -2, 5, -1, -2, 5, -1, -2, 5]`, and its sum is `11`, \n5. ... and so on\n\nThe only difference between cases when `k == m` and `k == m+1` is that: the best sub-array of the later contains one more `arr` and `bust_sum_[m+1] - best_sum[m]` is exactly `sum(arr)`.\n\nThus, it is safe to say, `res = kadane(arr * 2) + (k - 2) * sum(arr)` when `k >= 2` and `sum(arr) >= 0`. \n\nSo, what about the case when `sum(arr) < 0`, e.g., `arr = [1, -10, 3]` ? \n\nIn this case, the result is simply `res = kadane(arr * 2)` for any `k >= 2`, because `sum(arr) < 0` and any sub-array that contains `arr` will yield a smaller sum than one contains NO `arr`.\n\nCombine the above two possibilities, our result is therefore: `res = kadane(arr * 2) + (k - 2) * max(sum(arr), 0)` when `k >= 2` and `kadane(arr)` otherwise (do not forget to mod `10*9+7` before return the value).\n\n### Rust Solution\n```rust\nimpl Solution {\n    pub fn k_concatenation_max_sum(arr: Vec<i32>, k: i32) -> i32 {\n        let MOD = 1_000_000_007_i64;\n        let copy = arr.iter().map(|c| *c as i64).collect::<Vec<i64>>();\n        let mut best = 0_i64;\n        let mut cur = 0_i64;\n        let sum_i64: i64 = copy.iter().sum();\n        let k = k as usize;\n        \n        for i in 0..min(k, 2) * copy.len() {\n            let a = copy[i % arr.len()]; \n            cur = max(a, cur+a) % MOD;\n            best = max(best, cur) % MOD;\n        }\n        let res = if k > 1 { max(best, best + (k as i64 - 2) * max(sum_i64, 0)) % MOD } else {best % MOD};\n        res as i32\n    }\n}\n```\n\n
[]