3196. Maximize Total Cost of Alternating Subarrays Medium

1/**
2 * [3196] Maximize Total Cost of Alternating Subarrays
3 *
4 * You are given an integer array nums with length n.
5 * The cost of a <span data-keyword="subarray-nonempty">subarray</span> nums[l..r], where 0 <= l <= r < n, is defined as:
6 * cost(l, r) = nums[l] - nums[l + 1] + ... + nums[r] * (-1)^r - l
7 * Your task is to split nums into subarrays such that the total cost of the subarrays is maximized, ensuring each element belongs to exactly one subarray.
8 * Formally, if nums is split into k subarrays, where k > 1, at indices i1, i2, ..., ik - 1, where 0 <= i1 < i2 < ... < ik - 1 < n - 1, then the total cost will be:
9 * cost(0, i1) + cost(i1 + 1, i2) + ... + cost(ik - 1 + 1, n - 1)
10 * Return an integer denoting the maximum total cost of the subarrays after splitting the array optimally.
11 * Note: If nums is not split into subarrays, i.e. k = 1, the total cost is simply cost(0, n - 1).
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">nums = [1,-2,3,4]</span>
16 * Output: <span class="example-io">10</span>
17 * Explanation:
18 * One way to maximize the total cost is by splitting [1, -2, 3, 4] into subarrays [1, -2, 3] and [4]. The total cost will be (1 + 2 + 3) + 4 = 10.
19 * </div>
20 * <strong class="example">Example 2:
21 * <div class="example-block">
22 * Input: <span class="example-io">nums = [1,-1,1,-1]</span>
23 * Output: <span class="example-io">4</span>
24 * Explanation:
25 * One way to maximize the total cost is by splitting [1, -1, 1, -1] into subarrays [1, -1] and [1, -1]. The total cost will be (1 + 1) + (1 + 1) = 4.
26 * </div>
27 * <strong class="example">Example 3:
28 * <div class="example-block">
29 * Input: <span class="example-io">nums = [0]</span>
30 * Output: 0
31 * Explanation:
32 * We cannot split the array further, so the answer is 0.
33 * </div>
34 * <strong class="example">Example 4:
35 * <div class="example-block">
36 * Input: <span class="example-io">nums = [1,-1]</span>
37 * Output: <span class="example-io">2</span>
38 * Explanation:
39 * Selecting the whole array gives a total cost of 1 + 1 = 2, which is the maximum.
40 * </div>
41 *  
42 * Constraints:
43 * 
44 * 	1 <= nums.length <= 10^5
45 * 	-10^9 <= nums[i] <= 10^9
46 * 
47 */
48pub struct Solution {}
49
50// problem: https://leetcode.com/problems/maximize-total-cost-of-alternating-subarrays/
51// discuss: https://leetcode.com/problems/maximize-total-cost-of-alternating-subarrays/discuss/?currentPage=1&orderBy=most_votes&query=
52
53// submission codes start here
54
55impl Solution {
56    pub fn maximum_total_cost(nums: Vec<i32>) -> i64 {
57        
58    }
59}
60
61// submission codes end
62
63#[cfg(test)]
64mod tests {
65    use super::*;
66
67    #[test]
68    fn test_3196() {
69    }
70}
71