[LeetCode] 1913. Maximum Product Difference Between Two Pairs

https://leetcode.com/problems/maximum-product-difference-between-two-pairs/description/

Maximum Product Difference Between Two Pairs - LeetCode

leetcode - Maximum Product Difference Between Two Pairs

문제 유형 : 정렬 / 투포인터

문제 난이도 : Easy

 

문제

The product difference between two pairs (a, b) and (c, d) is defined as (a * b) - (c * d).

• For example, the product difference between (5, 6) and (2, 7) is (5 * 6) - (2 * 7) = 16.

Given an integer array nums, choose four distinct indices w, x, y, and z such that the product difference between pairs (nums[w], nums[x]) and (nums[y], nums[z]) is maximized.

Return the maximum such product difference.

 

두 쌍 (a, b)와 (c, d) 간의 연산 값은 (a*b) - (c*d)입니다.

 

정수 배열 nums가 주어집니다. 네 개의 서로 다른 인덱스를 골라서 얻는 연산값의 최대를 구하시오.

 

풀이

1. 정렬을 이용한 풀이 - 정렬을 해주고, 양 끝에서 두 개씩 값을 골라서 쌍을 만들어 연산한다 O(nlogn)

2. 반복문을 이용한 풀이 - 가장 큰 값, 두 번째로 큰 값, 가장 작은 값, 두 번째로 작은 값을 업데이트하면서 배열을 순회하고, 연산한다.

O(n)

 

 

코드

C++

static const int __ = []() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int maxProductDifference(vector<int>& nums) {
        const int n = nums.size();
        // sort(nums.begin(), nums.end());
        // return nums[n-1]*nums[n-2] - nums[0]*nums[1];

        int a = INT_MIN;
        int b = INT_MIN;
        int c = INT_MAX;
        int d = INT_MAX;

        for(int i = 0; i < n; i++) {
            if(nums[i] >= a) {
                b = a;
                a = nums[i];
            } else if(nums[i] > b) {
                b = nums[i];
            }

            if(nums[i] <= c) {
                d = c;
                c = nums[i];
            } else if(nums[i] < d) {
                d = nums[i];
            }
        }

        // cout << a << " " << b << " " << c << " " << d;

        return a*b-c*d;
    }
};