跳转至

3745. 三元素表达式的最大值

题目描述

给你一个整数数组 nums。

从 nums 中选择三个元素 a、b 和 c，它们的下标需 互不相同 ，使表达式 a + b - c 的值最大化。

返回该表达式可能的 最大值 。

 

示例 1：

输入： nums = [1,4,2,5]

输出： 8

解释：

可以选择 a = 4，b = 5，c = 1。表达式的值为 4 + 5 - 1 = 8，这是可能的最大值。

示例 2：

输入： nums = [-2,0,5,-2,4]

输出： 11

解释：

可以选择 a = 5，b = 4，c = -2。表达式的值为 5 + 4 - (-2) = 11，这是可能的最大值。

 

提示：

  • 3 <= nums.length <= 100
  • -100 <= nums[i] <= 100

解法

方法一：求最大值和次大值以及最小值

根据题目描述，我们需要选择三个互不相同下标的元素 \(a\)、\(b\) 和 \(c\)，使得表达式 \(a + b - c\) 的值最大化。

我们只需要遍历数组，找到最大的两个元素 \(a\) 和 \(b\) 以及最小的元素 \(c\)。然后计算表达式的值即可。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组的长度。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def maximizeExpressionOfThree(self, nums: List[int]) -> int:
        a = b = -inf
        c = inf
        for x in nums:
            if x < c:
                c = x
            if x >= a:
                a, b = x, a
            elif x > b:
                b = x
        return a + b - c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maximizeExpressionOfThree(int[] nums) {
        final int inf = 1 << 30;
        int a = -inf, b = -inf, c = inf;
        for (int x : nums) {
            if (x < c) {
                c = x;
            }
            if (x >= a) {
                b = a;
                a = x;
            } else if (x > b) {
                b = x;
            }
        }
        return a + b - c;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maximizeExpressionOfThree(vector<int>& nums) {
        const int inf = 1 << 30;
        int a = -inf, b = -inf, c = inf;
        for (int x : nums) {
            if (x < c) {
                c = x;
            }
            if (x >= a) {
                b = a;
                a = x;
            } else if (x > b) {
                b = x;
            }
        }
        return a + b - c;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func maximizeExpressionOfThree(nums []int) int {
    const inf = 1 << 30
    a, b, c := -inf, -inf, inf
    for _, x := range nums {
        if x < c {
            c = x
        }
        if x >= a {
            b = a
            a = x
        } else if x > b {
            b = x
        }
    }
    return a + b - c
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function maximizeExpressionOfThree(nums: number[]): number {
    const inf = 1 << 30;
    let [a, b, c] = [-inf, -inf, inf];

    for (const x of nums) {
        if (x < c) {
            c = x;
        }
        if (x >= a) {
            b = a;
            a = x;
        } else if (x > b) {
            b = x;
        }
    }
    return a + b - c;
}

评论