欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一组数中最小值与和的乘积最大的段

程序员文章站 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;
}