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
• 2. int[] shop2: an array of integers representing the second shop
• 3. 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:

15

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

Example 2

Input:

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

Output:

4

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;
    }
};

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:

6

Explanation: Explanation not found

Example 2

Input:

nums = [3, 2, 1]

Output:

3

Explanation: Explanation not found