[Rust] Intuitive explanation with development from O(n^2) to O(n) time and O(1) space
Solution 1A\n\nFor every spot i, compare it to all other spots j and calculate the score of the pair. Update the max_score found so far accordingly.\n\nrust\n  
### Solution 1A\n\nFor every spot `i`, compare it to all other spots `j` and calculate the score of the pair. Update the `max_score` found so far accordingly.\n\n```rust\n    pub fn max_score_sightseeing_pair(values: Vec<i32>) -> i32 {\n        let mut max_score = i32::MIN;\n        \n        for i in 0..values.len() {\n            for j in 0..values.len() {\n                if i == j { \n                    continue; \n                }\n                let (I, J) = (i as i32, j as i32);\n                max_score = cmp::max(max_score, values[i] + values[j] - (I - J).abs());\n            }\n        }\n        max_score\n    }\n```\nTime complexity: O(N^2)\n\nSpace complexity: O(1)\n\n### Solution 1B\n\nLet\'s observe that for every `i`, it is sufficient to only consider pairing with `j > i`.\nWhy ?\n- All pairs with `j < i` have already been considered since every `i` pairs with all `j > i`\n- `j == i` is not considered since they both refer to the same spot\n\n```rust\n    pub fn max_score_sightseeing_pair(values: Vec<i32>) -> i32 {\n        let mut max_score = i32::MIN;\n        \n        for i in 0..values.len() {\n            for j in i + 1..values.len() {\n                let (I, J) = (i as i32, j as i32);\n                max_score = cmp::max(max_score, values[i] + values[j] - (I - J).abs());\n            }\n        }\n        max_score\n    }\n```\nTime complexity: O(N^2)\n\nSpace complexity: O(1)\n\n### Solution 2A\nWe observe that with the inner for loop, we\'re asking the question: \n> For every `i`, what is the maximum score possible on pairing with a `j > i` (or `j` to the right of `i`) ? We then add `value[i]` to this `max_score`\n\nHow to find this maximum to the right of `i` ?\nLet\'s define an array `max_right` to store the maximum value to the right of every `i` to be `max(values[i], max_right[i + 1] - 1`. This includes its value. This makes sense since we\'ll query `max_right[i + 1]` from `max_right[i]`. \n`- 1` is to subtract the distance between `i` and `j`. \n\nSince we need `max_right[i + 1]` to calculate `max_right[i]`, we traverse the array from back to front. We\'re propagating the `max_right` seen so far from the `right` to the `left`. Therefore, we subtract 1 to account for the left shift in this \'propagation\'.\n\nConsider the following example:\n``` rust\n    let values = [8,1,5,2,6];\n```\n\nThe simplest `i` for which the above question can be answered is the last element in the array, `values[4] = 6` since there\'s no element to its right.\nWhat about `values[3] = 2` ? Only one `j` to its right so the `max_right` is `max(values[3], max_right[4] - 1) = 6 - 1 = 5`.\n\nHere\'s the complete table for all `i`:\n\n| `i`         | 0 | 1 | 2 | 3 | 4 |\n| ----------- | - | - | - | - | - |\n| `values`    | 8 | 1 | 5 | 2 | 6 |\n| `max_right` | 8 | 4 | 5 | 5 | 6 |\n\n\n``` rust\n    pub fn max_score_sightseeing_pair(values: Vec<i32>) -> i32 {\n        // max value to the right of i(including itself)\n        let mut max_right = values.clone(); \n        for i in (1..values.len() - 1).rev() {\n            max_right[i] = cmp::max(values[i], max_right[i + 1] - 1);\n        }\n        \n        let mut max_score = i32::MIN;\n        for i in (0..values.len() - 1).rev() - 1 {\n            max_score = cmp::max(max_score, values[i] + max_right[i + 1] - 1);\n        }\n        max_score\n    }\n```\n> `max_right[values.len() - 1] = values[values.len() - 1]`\n\n> `max_right[i]` is calculated up to index `i = 1` only since there\'s no index `-1` to lookup `max_right[0]`\n\nTime complexity: O(N)\n\nSpace complexity: 0(N)\n\n### Solution 2B\nSince we only lookup one index ahead, `max_right` does not need to be an array\n\n``` rust\n    pub fn max_score_sightseeing_pair(values: Vec<i32>) -> i32 {        \n        let mut max_score = i32::MIN;\n        let mut max_right = values[values.len() - 1];\n\n        for i in (0..values.len() - 1).rev() {\n            max_score = cmp::max(max_score, values[i] + max_right - 1);\n            max_right = cmp::max(values[i], max_right - 1);\n        }\n        max_score\n    }\n```\n\nTime complexity: O(N)\n\nSpace complexity: O(1)
['Rust']