2382. Maximum Segment Sum After Removals Hard

1/**
2 * [2382] Maximum Segment Sum After Removals
3 *
4 * You are given two 0-indexed integer arrays nums and removeQueries, both of length n. For the i^th query, the element in nums at the index removeQueries[i] is removed, splitting nums into different segments.
5 * A segment is a contiguous sequence of positive integers in nums. A segment sum is the sum of every element in a segment.
6 * Return an integer array answer, of length n, where answer[i] is the maximum segment sum after applying the i^th removal.
7 * Note: The same index will not be removed more than once.
8 *  
9 * Example 1:
10 * 
11 * Input: nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1]
12 * Output: [14,7,2,2,0]
13 * Explanation: Using 0 to indicate a removed element, the answer is as follows:
14 * Query 1: Remove the 0th element, nums becomes [0,2,5,6,1] and the maximum segment sum is 14 for segment [2,5,6,1].
15 * Query 2: Remove the 3rd element, nums becomes [0,2,5,0,1] and the maximum segment sum is 7 for segment [2,5].
16 * Query 3: Remove the 2nd element, nums becomes [0,2,0,0,1] and the maximum segment sum is 2 for segment [2]. 
17 * Query 4: Remove the 4th element, nums becomes [0,2,0,0,0] and the maximum segment sum is 2 for segment [2]. 
18 * Query 5: Remove the 1st element, nums becomes [0,0,0,0,0] and the maximum segment sum is 0, since there are no segments.
19 * Finally, we return [14,7,2,2,0].
20 * Example 2:
21 * 
22 * Input: nums = [3,2,11,1], removeQueries = [3,2,1,0]
23 * Output: [16,5,3,0]
24 * Explanation: Using 0 to indicate a removed element, the answer is as follows:
25 * Query 1: Remove the 3rd element, nums becomes [3,2,11,0] and the maximum segment sum is 16 for segment [3,2,11].
26 * Query 2: Remove the 2nd element, nums becomes [3,2,0,0] and the maximum segment sum is 5 for segment [3,2].
27 * Query 3: Remove the 1st element, nums becomes [3,0,0,0] and the maximum segment sum is 3 for segment [3].
28 * Query 4: Remove the 0th element, nums becomes [0,0,0,0] and the maximum segment sum is 0, since there are no segments.
29 * Finally, we return [16,5,3,0].
30 * 
31 *  
32 * Constraints:
33 * 
34 * 	n == nums.length == removeQueries.length
35 * 	1 <= n <= 10^5
36 * 	1 <= nums[i] <= 10^9
37 * 	0 <= removeQueries[i] < n
38 * 	All the values of removeQueries are unique.
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/maximum-segment-sum-after-removals/
44// discuss: https://leetcode.com/problems/maximum-segment-sum-after-removals/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn maximum_segment_sum(nums: Vec<i32>, remove_queries: Vec<i32>) -> Vec<i64> {
50        
51    }
52}
53
54// submission codes end
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn test_2382() {
62    }
63}
64