leetcode 2873. 有序三元组中的最大值 I

欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

  
标题描述

[2873] 有序三元组中的最大值 I

• https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-i/description
  

给你一个下标从 0 开始的整数数组 nums 。
请你从全部满意 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果全部满意条件的三元组的值都是负数，则返回 0 。
下标三元组 (i, j, k) 的值等于 (nums - nums[j]) * nums[k] 。
示例 1：
输入：nums = [12,6,1,2,7]
输出：77
解释：下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。
可以证明不存在值大于 77 的有序下标三元组。
示例 2：
输入：nums = [1,10,3,4,19]
输出：133
解释：下标三元组 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133 。
可以证明不存在值大于 133 的有序下标三元组。
示例 3：
输入：nums = [1,2,3]
输出：0
解释：唯一的下标三元组 (0, 1, 2) 的值是一个负数，(nums[0] - nums[1]) * nums[2] = -3 。因此，答案是 0 。
提示：
3 <= nums.length <= 100
1 <= nums <= 10^6
标题分析&信息发掘

由于数据较小，可以使用暴力枚举解决。
更进一步可能对公式进行分析
解题思绪

方法一 暴力枚举法

思绪

直接枚举，并判断巨细
注意

• 计算时要用long long类型
  

复杂度

• 时间复杂度：O(n^3)
  
• 空间复杂度：O(n)
  

代码实现

1. class Solution {
2. public:
3.     long long maximumTripletValue(vector<int>& nums) {
4.         long long res = 0;
5.         for(int i=0;i<nums.size();++i) {
6.             for(int j=i+1;j<nums.size();++j) {
7.                 if (nums[i]-nums[j]<=0)continue;
8.                 for( int k=j+1;k<nums.size();++k) {
9.                     long long v = nums[k];
10.                     v*=nums[i]-nums[j];
11.                     res = max(res, v);
12.                 }
13.             }
14.         }
15.         
16.         return res;
17.     }
18. };

复制代码

方法二 公式拆分+动态规划

思绪

可以考虑枚举 k, 然后去探求 nums-nums[j] (i<j<k) 的最大值。
那么，题目就转化为给定k 查寻nums-nums[j] (i<j<k) 的最大值。
可以维护一个premax数组，premax[x] 代表nums-nums[j] (i<j<=x) 的最大值。
递推公式
premax[0]=0,
premax[x] = max(max(nums[0…x-1])-nums[x], premax[x-1]).
注意

• 计算时要用long long类型
  

复杂度

• 时间复杂度：O(n)
  
• 空间复杂度：O(n)
  

代码实现

1. class Solution {
2. public:
3.     long long maximumTripletValue(vector<int>& nums) {
4.         long long res = 0;        
5.         vector<long long> premax(nums.size(), 0);
6.         int maxNum = 0;
7.         for(int i=0;i<nums.size();++i) {
8.             if(maxNum - nums[i]>0) premax[i] = maxNum - nums[i];
9.             if(i>1) premax[i] = max(premax[i], premax[i-1]);
11.             maxNum = max(maxNum, nums[i]);
12.         }
13.         for(int i=2;i<nums.size();++i) {
14.             if(premax[i-1]==0)continue;
15.             res = max(res, 1LL * nums[i]*premax[i-1]);
16.         }
18.         return res;
19.     }
20. };

复制代码

---

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。