2321. Maximum Score Of Spliced Array Hard

1/**
2 * [2321] Maximum Score Of Spliced Array
3 *
4 * You are given two 0-indexed integer arrays nums1 and nums2, both of length n.
5 * You can choose two integers left and right where 0 <= left <= right < n and swap the subarray nums1[left...right] with the subarray nums2[left...right].
6 *
7 * For example, if nums1 = [1,2,3,4,5] and nums2 = [11,12,13,14,15] and you choose left = 1 and right = 2, nums1 becomes [1,<u>12,13</u>,4,5] and nums2 becomes [11,<u>2,3</u>,14,15].
8 *
9 * You may choose to apply the mentioned operation once or not do anything.
10 * The score of the arrays is the maximum of sum(nums1) and sum(nums2), where sum(arr) is the sum of all the elements in the array arr.
11 * Return the maximum possible score.
12 * A subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).
13 *  
14 * Example 1:
15 *
16 * Input: nums1 = [60,60,60], nums2 = [10,90,10]
17 * Output: 210
18 * Explanation: Choosing left = 1 and right = 1, we have nums1 = [60,<u>90</u>,60] and nums2 = [10,<u>60</u>,10].
19 * The score is max(sum(nums1), sum(nums2)) = max(210, 80) = 210.
20 * Example 2:
21 *
22 * Input: nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]
23 * Output: 220
24 * Explanation: Choosing left = 3, right = 4, we have nums1 = [20,40,20,<u>40,20</u>] and nums2 = [50,20,50,<u>70,30</u>].
25 * The score is max(sum(nums1), sum(nums2)) = max(140, 220) = 220.
26 *
27 * Example 3:
28 *
29 * Input: nums1 = [7,11,13], nums2 = [1,1,1]
30 * Output: 31
31 * Explanation: We choose not to swap any subarray.
32 * The score is max(sum(nums1), sum(nums2)) = max(31, 3) = 31.
33 *
34 *  
35 * Constraints:
36 *
37 * n == nums1.length == nums2.length
38 * 1 <= n <= 10^5
39 * 1 <= nums1[i], nums2[i] <= 10^4
40 *
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/maximum-score-of-spliced-array/
45// discuss: https://leetcode.com/problems/maximum-score-of-spliced-array/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48use std::cmp;
49impl Solution {
50    pub fn maximums_spliced_array(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
51        let (mut sum1, mut sum2, mut first, mut second, mut max1, mut max2) = (0, 0, 0, 0, 0, 0);
52
53        for i in 0..nums1.len() {
54            first -= nums1[i] - nums2[i];
55            second += nums1[i] - nums2[i];
56
57            max1 = cmp::max(max1, first);
58            max2 = cmp::max(max2, second);
59
60            if first < 0 {
61                first = 0;
62            }
63            if second < 0 {
64                second = 0;
65            }
66            sum1 += nums1[i];
67            sum2 += nums2[i];
68        }
69
70        cmp::max(sum2 + max2, sum1 + max1)
71    }
72}
73
74// submission codes end
75
76#[cfg(test)]
77mod tests {
78    use super::*;
79
80    #[test]
81    fn test_2321() {
82        assert_eq!(
83            Solution::maximums_spliced_array(vec![6, 6, 6], vec![1, 9, 1]),
84            21
85        );
86    }
87}
88