3410. Maximize Subarray Sum After Removing All Occurrences of One Element Hard

1/**
2 * [3410] Maximize Subarray Sum After Removing All Occurrences of One Element
3 *
4 * You are given an integer array nums.
5 * You can do the following operation on the array at most once:
6 * 
7 * 	Choose any integer x such that nums remains non-empty on removing all occurrences of x.
8 * 	Remove all occurrences of x from the array.
9 * 
10 * Return the maximum <span data-keyword="subarray-nonempty">subarray</span> sum across all possible resulting arrays.
11 *  
12 * <strong class="example">Example 1:
13 * <div class="example-block">
14 * Input: <span class="example-io">nums = [-3,2,-2,-1,3,-2,3]</span>
15 * Output: <span class="example-io">7</span>
16 * Explanation:
17 * We can have the following arrays after at most one operation:
18 * 
19 * 	The original array is nums = [<span class="example-io">-3, 2, -2, -1, <u>3, -2, 3</u></span>]. The maximum subarray sum is 3 + (-2) + 3 = 4.
20 * 	Deleting all occurences of x = -3 results in nums = [2, -2, -1, <u><span class="example-io">3, -2, 3</span></u>]. The maximum subarray sum is 3 + (-2) + 3 = 4.
21 * 	Deleting all occurences of x = -2 results in nums = [<span class="example-io">-3, <u>2, -1, 3, 3</u></span>]. The maximum subarray sum is 2 + (-1) + 3 + 3 = 7.
22 * 	Deleting all occurences of x = -1 results in nums = [<span class="example-io">-3, 2, -2, <u>3, -2, 3</u></span>]. The maximum subarray sum is 3 + (-2) + 3 = 4.
23 * 	Deleting all occurences of x = 3 results in nums = [<span class="example-io">-3, <u>2</u>, -2, -1, -2</span>]. The maximum subarray sum is 2.
24 * 
25 * The output is max(4, 4, 7, 4, 2) = 7.
26 * </div>
27 * <strong class="example">Example 2:
28 * <div class="example-block">
29 * Input: <span class="example-io">nums = [1,2,3,4]</span>
30 * Output: <span class="example-io">10</span>
31 * Explanation:
32 * It is optimal to not perform any operations.
33 * </div>
34 *  
35 * Constraints:
36 * 
37 * 	1 <= nums.length <= 10^5
38 * 	-10^6 <= nums[i] <= 10^6
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/maximize-subarray-sum-after-removing-all-occurrences-of-one-element/
44// discuss: https://leetcode.com/problems/maximize-subarray-sum-after-removing-all-occurrences-of-one-element/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn max_subarray_sum(nums: Vec<i32>) -> i64 {
50        
51    }
52}
53
54// submission codes end
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn test_3410() {
62    }
63}
64