Service Now

01Find Max Minimum Value Using K Elements

You have given 2 Arrays Shop1 of size N and shop2 of size N and an Integer K. You have to find the maximum, minimum value using K elements from both given arrays. Calculate the minimum of the sum of K elements from both arrays, i.e., Min (a1+a2+...+ak, b1+b2+...+bk). Function Description Complete the function findMaxMinValueUsingKElements in the editor. findMaxMinValueUsingKElements has the following parameters:

1. int[] shop1: an array of integers representing the first shop
1. int[] shop2: an array of integers representing the second shop
1. int k: the number of elements to consider Returns int: the maximum minimum value using K elements

Constraints

A mysterous urban legend for now

Example 1

Input:

shop1 = [6, 3, 6, 5, 1]
shop2 = [1, 4, 5, 9, 2]
k = 3

Output:

Explanation: Min(6+6+5, 1+5+9) = 15.

Example 2

Input:

shop1 = [10, 2, 4]
shop2 = [1, 9, 6]
k = 1

Output:

Explanation: Min(4, 6) = 4.

解法

题意要求取出两数组各 k 个，使两边和的较小者最大。贪心：在每个数组分别取最大的 k 个元素求和，得到 s1、s2，答案 min(s1, s2)。把数组降序排序后取前 k 个即可。复杂度 O(n log n)，空间 O(1)。

from typing import List
import heapq

def find_max_min_value_using_k_elements(shop1: List[int], shop2: List[int], k: int) -> int:
    s1 = sum(heapq.nlargest(k, shop1))
    s2 = sum(heapq.nlargest(k, shop2))
    return min(s1, s2)

import java.util.*;

class Solution {
    int findMaxMinValueUsingKElements(int[] shop1, int[] shop2, int k) {
        return Math.min(topKSum(shop1, k), topKSum(shop2, k));
    }

    private long topKSum(int[] a, int k) {
        Integer[] arr = new Integer[a.length];
        for (int i = 0; i < a.length; i++) arr[i] = a[i];
        Arrays.sort(arr, Collections.reverseOrder());
        long s = 0;
        for (int i = 0; i < k; i++) s += arr[i];
        return s;
    }
}

class Solution {
public:
    int findMaxMinValueUsingKElements(vector<int>& shop1, vector<int>& shop2, int k) {
        return (int) min(topKSum(shop1, k), topKSum(shop2, k));
    }
private:
    long long topKSum(vector<int> a, int k) {
        sort(a.begin(), a.end(), greater<int>());
        long long s = 0;
        for (int i = 0; i < k; ++i) s += a[i];
        return s;
    }
};

02Maximum Sum of Balanced Subsequence

You are given a 0-indexed integer array nums. A subsequence of nums having length k and consisting of indices i_0 < i_1 < ... < i_k-1 is balanced if the following holds: nums[i] - nums[i-1] == i - (i-1), A subsequence of nums having length 1 is considered balanced. Return an integer denoting the maximum possible sum of elements in a balanced subsequence of nums. A subsequence of an array is a new non-empty array that is formed from the original array by deleting some (possibly none) of the elements without disturbing the relative positions of the remaining elements.

Constraints

Constraints not found

Example 1

Input:

nums = [1, 2, 3]

Output:

Explanation: Explanation not found

Example 2

Input:

nums = [3, 2, 1]

Output:

Explanation: Explanation not found

解法

条件 nums[i] - nums[j] == i - j ⇔ nums[i] - i == nums[j] - j。按差值 d = nums[i] - i 分组，每组内合法的子序列即为该组中所有正数之和(负数显然不选)。注意单元素子序列也合法，所以每组答案是 max(num_max_in_group, sum_of_positives)。最终答案是各组的最大值(题目说要求非空子序列，单数组允许选 1 个)。复杂度 O(n log n)，空间 O(n)。

from typing import List
from collections import defaultdict

def maximum_sum_of_balanced_subsequence(nums: List[int]) -> int:
    groups = defaultdict(list)
    for i, x in enumerate(nums):
        groups[x - i].append(x)
    ans = max(nums)
    for vals in groups.values():
        s = sum(v for v in vals if v > 0)
        m = max(vals)
        ans = max(ans, s if s > 0 else m)
    return ans

import java.util.*;

class Solution {
    long maximumSumOfBalancedSubsequence(int[] nums) {
        Map<Long, long[]> groups = new HashMap<>();
        long ans = Long.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            long key = (long) nums[i] - i;
            long[] arr = groups.computeIfAbsent(key, k -> new long[]{0L, Long.MIN_VALUE});
            if (nums[i] > 0) arr[0] += nums[i];
            arr[1] = Math.max(arr[1], nums[i]);
            ans = Math.max(ans, nums[i]);
        }
        for (long[] arr : groups.values()) {
            ans = Math.max(ans, arr[0] > 0 ? arr[0] : arr[1]);
        }
        return ans;
    }
}

class Solution {
public:
    long long maximumSumOfBalancedSubsequence(vector<int>& nums) {
        unordered_map<long long, pair<long long, long long>> groups;
        long long ans = LLONG_MIN;
        for (size_t i = 0; i < nums.size(); ++i) {
            long long key = (long long) nums[i] - (long long) i;
            auto& [posSum, mx] = groups[key];
            if (i == 0 || groups.count(key) == 0) mx = LLONG_MIN;
            if (nums[i] > 0) posSum += nums[i];
            if (nums[i] > mx) mx = nums[i];
            ans = max(ans, (long long) nums[i]);
        }
        for (auto& [k, p] : groups) {
            ans = max(ans, p.first > 0 ? p.first : p.second);
        }
        return ans;
    }
};