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⁵