一组数中最小值与和的乘积最大的段
程序员文章站
2022-05-12 10:40:55
...
一、ans = max(ans, min * sum)
一组数,找到一个区间,使这个区间的最小值 min 和这个区间的和 sum 的乘积 min * sum 最大,返回这个最大值。
输入
5
10 2 7 6 8
输出
126
解释
[7 6 8]
1、思路
二分法(最小值处分割)复杂度:nlogn
只有去掉最小值才可能出现更大的结果,去掉最小值,出现左右两部分。二分,最小值左边,最小值右边; 类似快排,nlogn
2、敲代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <climits>
using namespace std;
/*
输入
5
10 2 7 6 8
输出
126 [7 6 8]
*/
// 只有去掉最小值才可能出现更大的结果,去掉最小值,出现左右两部分
// 二分,最小值左边,最小值右边; 类似快排,nlogn
int ans = INT_MIN;
void dfs(vector<int> &nums, int left, int right)
{
if(left > right) return;
int sum_ = accumulate(nums.begin()+left, nums.begin()+right+1, 0); //求和
int pos = min_element(nums.begin()+left, nums.begin()+right+1) - nums.begin(); //最小值位置
int min_ = nums[pos]; //最小值
ans = max(ans, sum_*min_); //更新结果
dfs(nums, left, pos-1); //左侧
dfs(nums, pos+1, right); //右侧
}
int main()
{
int n;
cin >> n;
vector<int> nums(n);
for(int i=0; i<n; i++)
cin >> nums[i];
dfs(nums, 0, n-1);
cout << ans;
getchar();
return 0;
}
二、ans = max(ans, sum * avg)
一组数,找到一个区间,使这个区间的最小值 min 和这个区间的和 sum 的乘积 min * sum 最大,返回这个最大值。
1、思路
双指针,O(N)
去掉最左边和最右边其中一个最小的,sum减小,均值可能会增大。类似水坑问题,O(n)
2、敲代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <climits>
using namespace std;
/*
输入
5
1 2 3 7 8
输出
112.5 [7 8]
输入
5
6 3 3 7 8
输出
145.8
输入
5
1 3 10 7 8
输出
208.333
*/
// 双指针,去掉最左边和最右边其中一个最小的,sum减小,均值可能会增大。类似水坑问题,O(n)
int main()
{
int n;
cin >> n;
vector<int> nums(n);
for(int i=0; i<n; i++)
cin >> nums[i];
//双指针, O(N)
int left = 0;
int right = n-1;
double ans = INT_MIN;
double sum = accumulate(nums.begin()+left, nums.begin()+right+1, 0);
while(left < right)
{
//更新最大值
ans = max(ans, sum*sum/(right-left+1));
//指针对撞,最小的偏移
if(nums[left] <= nums[right])
{
sum -= nums[left];
left++;
}
else
{
sum -= nums[right];
right--;
}
}
cout << ans;
getchar();
return 0;
}