Write a function that returns a list of numbers from an array, excluding any sections that start with a 1 and extend to the next 0. Also, compute the sum of the numbers in the resulting list. Ignore any numbers from a 1 that is followed by another 1 until a 0 is found. Function Signature def ignore10(arr): Parameters

• arr (List[int]): An array of integers from which sections will be ignored as described. Returns Tuple[List[int], int]: A tuple containing the modified array and the sum of its elements.

Constraints

• 1 ≤ arr.length ≤ 10⁵
• -10⁹ ≤ arr[i] ≤ 10⁹

Example 1

Input:

arr = [6, 1, 7, 0, 2, 5, 6, 1, 3]

Output:

([6, 2, 5, 6, 1, 3], 23)

Explanation: The numbers between the first 1 and the next 0 (inclusive) are ignored, which are 1, 7, 0. The subsequent 1 is not followed by a 0, hence it and the numbers following it are included.

Example 2

Input:

arr = [4, 0, 6, 1, 4, 6, 1, 2]

Output:

([4, 0, 6, 1, 2], 13)

Explanation: There is no 1 followed by 0 that encloses numbers to ignore. All numbers are included.

Example 3

Input:

arr = [4, 0, 6, 1, 2, 4, 1, 1, 3, 0, 2]

Output:

([4, 0, 6, 2], 12)

Explanation: The sequence starting with 1 at index 3 ends with 0 at index 9. All numbers between these indices are ignored.

Example 4

Input:

arr = [0, 6, 1, 1, 9, 1, 3, 0, 2]

Output:

([0, 2], 2)

Explanation: The numbers between the first 1 and the next 0 (inclusive) are ignored, which includes all numbers from the first 1 to the 0.

解法

单趟扫描 + 状态机：skipping = False。遇到 1 且未在 skip 中时，向前查找下一个 0：若存在，跳过 [当前 1, 该 0](含两端)；若不存在，则保留剩余所有元素。否则正常收集。复杂度 O(n)，空间 O(n)。

from typing import List, Tuple

def ignore10(arr: List[int]) -> Tuple[List[int], int]:
    res = []
    i = 0
    n = len(arr)
    while i < n:
        if arr[i] == 1:
            j = i + 1
            while j < n and arr[j] != 0:
                j += 1
            if j < n:
                i = j + 1
            else:
                break
        else:
            res.append(arr[i])
            i += 1
    return res, sum(res)

import java.util.*;

class Solution {
    Object[] ignore10(int[] arr) {
        List<Integer> res = new ArrayList<>();
        int i = 0, n = arr.length;
        while (i < n) {
            if (arr[i] == 1) {
                int j = i + 1;
                while (j < n && arr[j] != 0) j++;
                if (j < n) i = j + 1; else break;
            } else { res.add(arr[i]); i++; }
        }
        int s = 0; for (int x : res) s += x;
        return new Object[]{res, s};
    }
}

class Solution {
public:
    pair<vector<int>, int> ignore10(vector<int>& arr) {
        vector<int> res;
        int i = 0, n = arr.size();
        while (i < n) {
            if (arr[i] == 1) {
                int j = i + 1;
                while (j < n && arr[j] != 0) ++j;
                if (j < n) i = j + 1; else break;
            } else { res.push_back(arr[i]); ++i; }
        }
        int s = 0; for (int x : res) s += x;
        return {res, s};
    }
};

A software development firm is hiring engineers and used the following challenge in its online test. Given an array arr that contains n integers, the following operation can be performed on it any number of times (possibly zero).

• Choose any index 0 ≤ i < n and swap arr[i] and arr[j].
• Each element of the array can be swapped at most once during the whole process. The strength of an index is defined as arr[i] * (i + 1), using 0-based indexing. Find the maximum possible sum of the strength of all indices after optimal swaps. Mathematically, maximize the following: ∑_i=0^n-1 arr[i] * (i + 1) Example Consider n = 4, arr = [2, 1, 4, 3]. It is optimal to swap (arr[2], arr[3]) and (arr[0], arr[1]). The final array is [1, 2, 3, 4]. The sum of strengths = (1 * 1 + 2 * 2 + 3 * 3 + 4 * 4) = 30, which is maximum possible. Thus, the answer is 30. Function Description Complete the function getMaximumSumOfStrengths in the editor below. getMaximumSumOfStrengths has the following parameter:
• int arr[n]: the initial array Returns
• long int: the maximum possible sum of strengths of all indices after the operations are applied optimally

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ arr[i] ≤ 10⁵

解法

每个元素最多参与一次交换 ⇒ 交换关系形成不相交配对集合。要让 ∑ arr[i] * (i+1) 最大，配对内部要把更大的值放到更大的下标上。最优策略：把数组排序后保持原序索引位置等价于 “整体排序”，因为我们总能用一系列两两交换把任意排列变成排序后的形式(前提是每元素最多 1 次交换 ⇒ 该排列由交换形成的置换是若干 transposition；用任意 transposition 序列即可，但因为这里每个元素只允许至多一次交换，这意味着可以实现任意置换中循环长度 ≤ 2 的部分；可仔细证明上界 = 排序后数组)。综上，对 arr 升序排序，答案 = ∑ (i+1) * arr[i]。复杂度 O(n log n)。

from typing import List

def get_maximum_sum_of_strengths(arr: List[int]) -> int:
    sorted_arr = sorted(arr)
    return sum((i + 1) * v for i, v in enumerate(sorted_arr))

import java.util.*;

class Solution {
    long getMaximumSumOfStrengths(int[] arr) {
        int[] a = arr.clone();
        Arrays.sort(a);
        long s = 0;
        for (int i = 0; i < a.length; i++) s += (long) (i + 1) * a[i];
        return s;
    }
}

class Solution {
public:
    long long getMaximumSumOfStrengths(vector<int>& arr) {
        vector<int> a = arr;
        sort(a.begin(), a.end());
        long long s = 0;
        for (size_t i = 0; i < a.size(); ++i) s += (long long)(i + 1) * a[i];
        return s;
    }
};