3695. Maximize Alternating Sum Using Swaps Hard

1/**
2 * [3695] Maximize Alternating Sum Using Swaps
3 *
4 * You are given an integer array nums.
5 * You want to maximize the alternating sum of nums, which is defined as the value obtained by adding elements at even indices and subtracting elements at odd indices. That is, nums[0] - nums[1] + nums[2] - nums[3]...
6 * You are also given a 2D integer array swaps where swaps[i] = [pi, qi]. For each pair [pi, qi] in swaps, you are allowed to swap the elements at indices pi and qi. These swaps can be performed any number of times and in any order.
7 * Return the maximum possible alternating sum of nums.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">nums = [1,2,3], swaps = [[0,2],[1,2]]</span>
12 * Output: <span class="example-io">4</span>
13 * Explanation:
14 * The maximum alternating sum is achieved when nums is [2, 1, 3] or [3, 1, 2]. As an example, you can obtain nums = [2, 1, 3] as follows.
15 * 
16 * 	Swap nums[0] and nums[2]. nums is now [3, 2, 1].
17 * 	Swap nums[1] and nums[2]. nums is now [3, 1, 2].
18 * 	Swap nums[0] and nums[2]. nums is now [2, 1, 3].
19 * </div>
20 * <strong class="example">Example 2:
21 * <div class="example-block">
22 * Input: <span class="example-io">nums = [1,2,3], swaps = [[1,2]]</span>
23 * Output: <span class="example-io">2</span>
24 * Explanation:
25 * The maximum alternating sum is achieved by not performing any swaps.
26 * </div>
27 * <strong class="example">Example 3:
28 * <div class="example-block">
29 * Input: <span class="example-io">nums = [1,1000000000,1,1000000000,1,1000000000], swaps = []</span>
30 * Output: <span class="example-io">-2999999997</span>
31 * Explanation:
32 * Since we cannot perform any swaps, the maximum alternating sum is achieved by not performing any swaps.
33 * </div>
34 *  
35 * Constraints:
36 * 
37 * 	2 <= nums.length <= 10^5
38 * 	1 <= nums[i] <= 10^9
39 * 	0 <= swaps.length <= 10^5
40 * 	swaps[i] = [pi, qi]
41 * 	0 <= pi < qi <= nums.length - 1
42 * 	[pi, qi] != [pj, qj]
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/maximize-alternating-sum-using-swaps/
48// discuss: https://leetcode.com/problems/maximize-alternating-sum-using-swaps/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52impl Solution {
53    pub fn max_alternating_sum(nums: Vec<i32>, swaps: Vec<Vec<i32>>) -> i64 {
54        
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_3695() {
66    }
67}
68