无脑常规暴力破解方法:
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
int maximum = INT_MIN;
for(int i = 0;i < n;i++)
{
for(int j = i + 1;j < n;j++)
{
maximum = max(maximum,(nums[i] - 1) * (nums[j] - 1));
}
}
return maximum;
}
};
运行速度也是符合预期,仅击败8.69%C++提交。
Runtime: 48 ms, faster than 8.69% of C++ online submissions for Maximum Product of Two Elements in an Array.
Memory Usage: 10.3 MB, less than 8.07% of C++ online submissions for Maximum Product of Two Elements in an Array.
这里我们注意到nums中的值都是正数,可以将程序优化为只遍历一遍,找到最大值和次大值即可。
class Solution {
public:
int maxProduct(vector<int>& nums) {
int m = INT_MIN,n = INT_MIN;
for(auto num : nums)
{
if(num > m)
n = exchange(m,num);
else
n = max(n,num);
}
return (m - 1) *(n - 1);
}
};
这里的exchange和swap的区别是exchange返回的是旧值。