首页 > 试题广场 >

编程题2

[编程题]编程题2
  • 热度指数:11020 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解

给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个:

区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可,不需要输出具体的区间。如给定序列  [6 2 1]则根据上述公式, 可得到所有可以选定各个区间的计算值:

 

[6] = 6 * 6 = 36;

[2] = 2 * 2 = 4;

[1] = 1 * 1 = 1;

[6,2] = 2 * 8 = 16;

[2,1] = 1 * 3 = 3;

[6, 2, 1] = 1 * 9 = 9;

 

从上述计算可见选定区间 [6] ,计算值为 36, 则程序输出为 36。

区间内的所有数字都在[0, 100]的范围内;


输入描述:
第一行输入数组序列长度n,第二行输入数组序列。
对于 50%的数据,  1 <= n <= 10000;
对于 100%的数据, 1 <= n <= 500000;


输出描述:
输出数组经过计算后的最大值。
示例1

输入

3
6 2 1

输出

36
#include<iostream>
#include<vector>
using namespace std;
int main() {
	int eNum = 0;
	scanf("%d", &eNum);
	int* list = new int[eNum];
	int count[101] = { 0 };
	for (int i = 0; i < eNum; i++) {
		scanf("%d", &list[i]);
		count[list[i]]++;
	}
	vector<int> num;
	for (int i = 0; i < 101; i++) {
		if (count[i] != 0)
			num.push_back(i);
	}
	int max = 0;
	for (int i = 0; i < num.size(); i++) {
		int min = 100;
		int sum = 0;
		for (int j = 0; j <= eNum; j++) {
			if (list[j] < num[i] || j == eNum) {
				max = min * sum > max ? min*sum : max;
				sum = 0; min = 100;
			}
			else {
				min = min < list[j] ? min : list[j];
				sum += list[j];
			}
		}
	}
	printf("%d", max);
	return 0;
}
首先对数据进行桶排序,然后根据桶里的元素对数组进行遍历,当当前遍历的数组元素大于当前桶的值时,对区间进行计算。桶排可以过滤掉定义域内数组中没有出现的元素,不过由于样本数量比较大,基本上每个数据都会出现一次故其实这一步可以省略。
编辑于 2019-09-18 03:03:01 回复(0)
我就问一句,有python通过的吗,python是快的时候快的不得了,慢的时候慢的慢的不得了
 if __name__ == '__main__':
    n=int(input())
    array=list(map(int,input().split(" ")))
    result=0
    for i in range(n):
        sum=array[i]
        j=i-1
        k=i+1
        while(j>=0):
            if array[j]>=array[i]:
                sum+=array[j]
                j=j-1
            else:
                break
        while(k<n):
            if array[k]>=array[i]:
                sum+=array[k]
                k=k+1
            else:
                break
        result=max(result,sum*array[i])
    print(result)

发表于 2019-03-02 14:10:07 回复(4)

单调队列,两边延展。

#include <bits/stdc++.h>

using namespace std;
int num[500000];
int sum[500000];
int lt[500000];
int rt[500000];

stack<pair<int,int>> S;
stack<pair<int,int>> SR;
int sum_of(int l, int r){
    if (l == 0)return sum[r];
    else return sum[r] - sum[l - 1];
}
int main(){
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++){
        scanf("%d", &num[i]);
        if(i == 0){
            sum[i] = num[i];
        } else {
            sum[i] = sum[i - 1] + num[i];
        }
    }

    for (int i = 0; i < N; i++){
            while(!S.empty() && S.top().second >= num[i]){
                S.pop();
            }
            if(!S.empty()){
                lt[i] = S.top().first + 1;
            }else{
                lt[i] = 0;
            }
            S.push(make_pair(i,num[i]));

    }
    for (int i = N - 1; i >= 0; i--){
            while(!SR.empty() && SR.top().second >= num[i]){
                SR.pop();
            }
            if(!SR.empty()){
                rt[i] = SR.top().first - 1;
            } else{
                rt[i] = N - 1;
            }
            SR.push(make_pair(i,num[i]));
    }
    long long ans = 0;
    for (int i = 0; i < N; i++){
        ans = max(ans, (long long)sum_of(lt[i],rt[i]) * (long long)num[i]);
    }
    cout<<ans<<endl;
    return 0;
}
发表于 2018-05-03 13:44:53 回复(0)
/*题目意思是区间中的最小数乘以区间所有数的和,那么输入数组序列里的n数都可能是区间里的最小数
所以,将数组从小到大排列,a[i]乘以比它大的数之和,也即数组中在它后面的数,求得这n个乘
积中的最大值即要输出的最大值。另外,可以将比a[i]大的所有数之和统一计算减少重复计算。*/
//只是不知道以下测试用例为什么出现这样的结果,手动计算的最大值也是20384啊,哪位路过的大神能否给个解答?感谢。
/*测试用例:
10
81 87 47 59 81 18 25 40 56 0 
对应输出应该为:
16685
你的输出为:
20384*/
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include<vector>
using namespace std;

int main() {
    int n,k,sum=0,imax=0,max=0;
    cin >> n;
    vector<int>a,b;
    for(int i=0;i<n;i++) {
        cin>> k;
        a.push_back(k);
    }

    sort(a.begin(), a.end());  //默认从小到大排序
    for (int i = n-1; i >=0 ; i--) {
        sum = sum + a[i];
        b.push_back(sum);
    }
    for (int i = 0; i < n; i++) {
        imax = a[i] * b[n - i - 1];
        if (imax > max)
            max = imax;
    }
    cout << max << endl;
    return 0;
}
 
发表于 2018-06-22 20:51:01 回复(10)
考虑到每一个答案都是由一个区间的最小值×区间和得出
那么在一个给定的区间最小值情况下,最优情况一定是这个区间尽可能的延伸,直至区间最小值不满足给定值。
题目中数组里的数范围是[0, 100]。所以我们对每一个可能的区间最小值扫描一遍数组,每找到一个符合条件的区间就更新答案。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5e5 + 5;
int a[MAX_N];
int main() {
    long long ans, sum;
    int n, minnum;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    a[n] = 0;
    ans = 0;
    for (int j = 100; j >= 1; j--) {
        sum = 0, minnum = 101;
        for (int i = 0; i <= n; i++) {
            if (a[i] < j) {
                ans = max(ans, sum * minnum);
                minnum = 101, sum = 0;
            }
            else {
                sum += a[i];
                minnum = min(minnum, a[i]);
            }
            //printf("i = %d, j = %d, ans = %lld\n", i, j, ans);
        }

    }
    printf("%lld\n", ans);
    return 0;
}

发表于 2018-02-04 13:43:41 回复(6)
先找出数组中每一个数字所对应的最大范围然后与该位置的数字相乘存在另一个数组中,遍历这个数组可得
import java.util.Scanner;

public class Main {
    
    public static void main(String srg[]) {
        
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext())
        {
            int n = sc.nextInt();
            int a[] = new int[n];
            int b[] = new int[n];
            for (int i = 0;i < n;i++)
            {
                a[i] = sc.nextInt();
            }
            for(int i = 0;i < n;i++)
            {
                int p = i,q = i+1,sum = 0;
                while(p >=0&&a[i] <= a[p])
                {
                    sum += a[p];
                    p--;
                }
                while(q < n&&a[i] <= a[q])
                {
                    sum += a[q];
                    q++;
                }
                b[i] = a[i] * sum;
            }
            int max = b[0];
            for(int i = 1;i < n;i++)
            {
                if(b[i] > max)
                    max = b[i];
            }
            System.out.println(max);
        }
    }
}
发表于 2018-05-09 15:29:25 回复(2)
思路似乎跟大佬们有区别
我是采用每个点作为最小值,往前,往后找直到最小值不是该点为止(临界点不取)
然后把这个区间和这个最小值相乘相加
答案也是对的
import java.util.*;

public class Main{
    
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] num=new int[n];
        sc.nextLine();
        for(int i=0;i<n;i++){
            num[i]=sc.nextInt();
        }
        int max=Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            //每个值,作为区间min值,找到最大的区间
            int l=i-1;
            while(l>=0){
                if(num[l]>=num[i]){
                    l--;
                }
                else{
                    break;
                }
            }
            //break这个就是不合适的
            l=l+1;
            int r=i+1;
            while(r<n){
                if(num[r]>=num[i]){
                    r++;
                }
                else{
                    break;
                }
            }
            //break这个就是不合适的
            r=r-1;
            int thismax=0;
            for(int j=l;j<=r;j++){
                thismax+=num[j];
            }
            thismax*=num[i];
            max=Math.max(max,thismax);
        }
        System.out.println(max);
    }
    
}
发表于 2019-07-09 23:02:41 回复(2)
#如果当前数小于栈顶元素,或者遍历结束但栈不为空,栈顶元素出栈,作为区间最小值,同时它也是区间的右边界,区间的左边界为出栈后栈顶下标-1。
#如果栈为空或者当前数大于等于栈顶元素,下标入栈
n = int(input())
value = list(map(int,input().split()))
p = [value[0]]
for i in range(1,n):  #预处理累计求和
    p.append(p[i-1] + value[i])
ans = 0
stack = [0]
for i in range(1,n):
    while stack and value[stack[-1]]>=value[i]: # 栈非空且栈顶元素大于当前元素,为了维持单调递增栈,弹出栈顶元素
        min_num = value[stack.pop()]# 栈顶元素为区间最小值,出栈。左边界为栈顶或者空
        ans = max(ans,(p[i-1]-(p[stack[-1]] if len(stack)>0 else 0))*min_num) 
    stack.append(i)
print(ans)

发表于 2019-04-13 19:00:08 回复(3)
import java.util.Scanner;
import java.util.Stack;

public class Main {
    /*区间最小值与区间之和相乘的最大值*/
    public static void main(String[] args) {
        Scanner scanner = new Scanner (System.in);
        int n = scanner.nextInt ();
        int[] arr = new int[n];
        int[] sum = new int[n+1];//累加和
        sum[0] = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt ();
            sum[i+1] = arr[i]+sum[i];
        }
        int[][] help = new int[n][2];
        Stack<Integer> s = new Stack<> ();
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            while (!s.isEmpty ()&&arr[i]<=arr[s.peek ()]){
                int j = s.pop ();
                help[j][0] = s.isEmpty ()?-1:s.peek ();
                help[j][1] = i;
            }
            s.push (i);
        }
        while (!s.isEmpty ()){
            int tmp  =s.pop ();
            help[tmp][0] = s.isEmpty ()?-1:s.peek ();
            help[tmp][1] = n;
        }
        for (int i = 0; i < help.length; i++) {
            int left = help[i][0];
            int right = help[i][1];
            max = Math.max (max,arr[i]*(sum[right]-sum[left+1]));
        }
        System.out.println (max);
    }
}
//参考自程序员代码面试指南。单调栈结构+辅助数组存储累加和,时间复杂度n,每个数组元素只需要入栈出栈一次。
发表于 2019-09-02 14:26:23 回复(0)

c++ 递归

先思考一个规律:
例如,对于数组【6,2,1】,当我们已知,其左端为6,右端为1,计算结果为1*(6+2+1)=9时,下一步应该如何调整下标来搜索可能更大的计算结果呢?
显然,我们应该比较左端和右端,舍弃较小的一端。搜索【6,2】,得到结果2*(6+2)=16。
当我们舍弃1时,虽然数组和变小,但是最小值却变大了,乘积才可能变大。

这告诉我们,必须去掉当前数组中的最小值,才可能得到更大的结果!

这是因为,计算结果 = 最小值 * 数组和。
当我们由外向内搜索时,数组和一定在减少,想要结果变大,最小值就势必变大。
例如,对于数组【6,1,2】。无论是【6,1】,还是【1,2】,都是小于原数组的。这就是因为原来的最小值,仍在数组中,而数组和减小了。

由此我们可以得到递归的规律。当我们已经计算了某一个区间[left,right]后,不妨记为result1,
(1)搜索当前区间的最小值位置pos
(2)用pos分割当前的区间得到[left,pos-1]和[pos+1,right]
(3)递归计算分割后的区间结果,记为result2和result3
(4)取result1、result2和result3中的最大值,作为当前区间的结果
这里,递归结束的标志应该是,某个区间已经区分不出最小值。有两种情况:
(1)该区间内仅有一个数,left=right
(2)该区间内的所有数均相等

代码如下:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int mymax(vector& num, int left, int right)
{
    if(left == right) return num[left]*num[left];  //若区间内仅有一个数,结束递归
    bool flag = true;
    for(int i=left;i<right;i++)
        if(num[i] != num[i+1])
        {
            flag = false;
            break;
        }
    if(flag) return num[left]*num[left]*(right-left+1);  //若区间内的数全部相等,结束递归
    int result = num[left];
    int minval = num[left];
    int pos = left;
    for(int i = left+1;i<=right;i++)  //搜索区间内的最小值
    {
        if(num[i]<minval)
        {
            minval = num[i];
            pos = i;
        }
        result += num[i];
    }
    result = result * minval;  //计算当前区间
    if(pos != left) result = max(result, mymax(num, left, pos-1));  //计算最小值左边
    if(pos != right) result = max(result, mymax(num, pos+1, right));  //计算最小值右边
    return result;
}
int main()
{
    int n;
    cin >> n;
    vector num(n, 0);
    for(int i=0;i> num[i];
    int left = 0;
    int right = n - 1;
    cout << mymax(num, left, right);
    return 0;
}
欢迎大佬来改进!
发表于 2021-06-24 15:33:36 回复(0)
单调栈做法,写得有点繁琐了。……看了评论区的大佬才发现数范围是[0,100]
#include<iostream>
#include<stdio.h>
#include<vector>
#include<stack>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> arr(n,0);
    for(int i=0;i<n;i++)
        cin>>arr[i];
    vector<int> sum(n+1,0); //前缀和,sum[i]表示arr[0]...arr[i-1]之和(不含arr[i])
    sum[0]=0;
    for(int i=1;i<=n;i++) {
        sum[i]+=sum[i-1]+arr[i-1];
    }
    vector<int> left(n,0); //left[i]:当以arr[i]为最小值时所能形成的区间的左边界
    vector<int> right(n,0); //right[i]:当以arr[i]为最小值时所能形成的区间的右边界
    //左右边界为闭区间(包含)
    stack<int> s; //单调栈
    for(int i=1;i<n;i++) {
        while(!s.empty() && arr[s.top()]>arr[i]) {
            int x=s.top(); s.pop();
            //栈顶元素比当前值大,所以栈顶元素为min时的右边界必为i-1
            right[x]=i-1;
        }
        if(!s.empty()) {
            int x=s.top(); //此时栈顶arr[x]<=arr[i],所以arr[i]的左边界为x+1(等号不用担心,重复的值必有一个会取到包含这些重复数的最大区间)
            left[i]=x+1;
        }else{//左边不存在其他值比当前值小,所以直接拉到0
            left[i]=0;
        }
        s.push(i);
    }
    while(!s.empty()) {
        int x=s.top(); s.pop();
        right[x]=n-1;
    }
    int res=0;
    for(int i=0;i<n;i++) {
        res=max(res,arr[i]*(sum[right[i]+1]-sum[left[i]]));
    }
    cout<<res;
    return 0;
}
发表于 2021-05-17 20:39:53 回复(0)

思路
每个元素都可能是某个或多个区间的最小值,所以当最小值确定的时候,区间越大越好,可以固定每个最小值,然后找区间左边界和右边界。

#include<iostream>
#include<vector>
#include<limits.h>
#include<algorithm>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i=0; i<n; i++) cin>>nums[i];
    // 每次假设当前为最小
    int cur_max = -1;
    for(int i=0; i<n; i++){
        // 假设nums[i]是某个区间的最小值,那么这个区间应该越大越好,所以可以来找区间的左边界和右边界
        int l = i;
        while(l>=0 && nums[l]>=nums[i]) l--;// 确定左边界
        int r = i;
        while(r<n && nums[r]>=nums[i]) r++;// 确定右边界
        int sum = accumulate(nums.begin()+l+1, nums.begin()+r, 0);
        cur_max = max(cur_max, sum*nums[i]);
    }
    cout<<cur_max<<endl;
    return 0;
}
发表于 2019-07-18 23:02:34 回复(0)
# 为了找到所有“最大的”点,可以遍历点集合 P,对于每个点 x,检查是否满足所有其他点都不在 x 的右上方区域内。 def find_max_points(points):
    def is_max_point(p, others):
        for other in others:
            if other[0] > p[0] and other[1] > p[1]:
                return False
        return True

    max_points = []

    for i in range(len(points)):
        if is_max_point(points[i], points[:i] + points[i+1:]):
            max_points.append(points[i])

    return max_points

points = [(1, 2), (2, 3), (3, 1), (4, 4), (5, 3)]
result = find_max_points(points)
print(result)
直接暴力解题,只要其他节点没有横纵坐标同时大于当前坐标的,就将它添加到结果里面
发表于 2023-12-22 15:29:21 回复(0)
用了以下三种方法,通过率分别为20%, 50%, 60%,看来python还是太慢了。。。
n = int(input())
inp = list(map(int, input().split()))
max_num = 0
'''
## brute force method O(n^3)
for i in range(1,n+1):
    for j in range(0,n-i+1):
        temp = min(inp[j:j+i]) * sum(inp[j:j+i])
        if temp > max_num:
            max_num = temp
'''

'''
## O(n^2)
for i in range(n):
    left_index = i
    right_index = i
    while left_index > 0:
        if inp[left_index -1] < inp[i]:
            break
        else :
            left_index -= 1
    while right_index < n-1:
        if inp[right_index +1] < inp[i]:
            break
        else :
            right_index += 1
    temp = min(inp[left_index:right_index+1]) * sum(inp[left_index:right_index+1])
    if temp > max_num:
        max_num = temp
'''
# O(n)
for i in range(0,101):
    min_num = 101
    sum1 = 0
    for j in range(n):
        if inp[j] < i :
            max_num = max(max_num, sum1 * min_num)
            sum1 = 0
            min_num = 101
        else :
            sum1 += inp[j]
            min_num = min(min_num, inp[j])
            
print(max_num)

发表于 2019-02-21 20:26:32 回复(0)
'''
为什么我这个跑出来是0,然后他给我的
用例输入
10
81 87 47 59 81 18 25 40 56 0 
预期输出
16685                这个预期输出结果是错的吧,并不是最大值啊,
                          我看了一下这个结果的区间是[81, 87, 47, 59, 81]  ——> 47*(81+87+47+56+81)
实际输出
20384              而我这个区间是[81, 87, 59, 81, 56]  ——>  56*(81+87+59+81+56)
                         这个才是最大值吧,还是说我理解错了
我的理解是给定数组,分别按公式求所有非空子集的列表最小值✖列表所有元素之和,然后输出最大值。
有大佬能看看我的理解正确吗?
'''
import itertools
def generate_subsets(nums):
    subsets = []
    for r in range(1, len(nums) + 1):
        subsets.extend(list(itertools.combinations(nums, r)))
    return [list(subset) for subset in subsets]
n = int(input())
numbers = list(map(int, input().split(' ')[:n]))
subsets = generate_subsets(numbers)
product_sums = []
for subset in subsets:
    product_sums.append(min(subset) * sum(subset))
maximum_product_sum = max(product_sums)
print(maximum_product_sum)
编辑于 2023-11-23 15:48:05 回复(0)
def max_val(li):
    if len(li) == 1:
        return li[0]**2
    m = min(li)
    ind = li.index(m)
    if ind == 0:
        return max(sum(li)*m,max_val(li[1:]))
    elif ind == len(li) - 1:
        return max(sum(li)*m,max_val(li[:-1]))
    else:
        return max(sum(li)*m,max_val(li[:ind]),max_val(li[ind+1:]))

n = int(input())
nums = list(map(int,input().strip().split(' ')))
print(max_val(nums))
用递归做的,跑到第七组的时候内存超了。。。。

发表于 2023-09-05 23:42:26 回复(0)
# 思路:遍历每一个元素,保证当前元素为最小值,然后向两边扩展
while True:
    try:
        length = int(input())
        nums = list(map(int, input().split()))
        max_v = -1
        pos = 0
        while pos < length:
            left, right = pos - 1, pos + 1
            count = nums[pos]
            if not count:    # 关键的一步,必须有,否则超时
                if count > max_v: max_v = count
                pos += 1
                continue
            while left >= 0 and nums[left] >= nums[pos]:
                count += nums[left]
                left -= 1
            while right < length and nums[right] >= nums[pos]:
                count += nums[right]
                right += 1
            if count * nums[pos] > max_v: max_v = count * nums[pos]
            pos += 1
        print(max_v)
    except Exception as e:
        break

发表于 2023-07-21 09:56:38 回复(0)
#include <bits/stdc++.h>
using namespace std;
const int N=500010;
int a[N];
stack<int> cur,l; //cur是单调栈,l是和cur同步的栈,记录cur中元素的左边比它大的数的和 
int tempSum=0;
int n;
int ans=0;
void POP()
{
	int num=cur.top(); cur.pop();
	int leftOfNum=l.top();l.pop();
	int all=leftOfNum+num+tempSum; //左+中+右 
	ans=max(ans,num*all);
	tempSum+=num+leftOfNum;
}

int main() 
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    a[n]=0;
    
    //定义一个组的中心是组中最小的数,这样就可以用单调栈 
    tempSum=0;
    for(int i=0;i<=n;i++)
    {
    	//把当前数左边(比它大)部分的pop出去,并把左边的值存用来计算tempSum,pop完后会tempSum入l栈并归零 
		//右边的会比它先弹出去并计算出新的tempSum,等到它被pop需要计算和时tempSum就是右边的和了 
		int num=a[i];
		while(!cur.empty()&&cur.top()>num)
			POP();
		cur.push(num);
		l.push(tempSum);
		tempSum=0;
	}
	cout<<ans;
}
/*
6
1 3 4 2 6 5
*/

发表于 2023-03-16 14:22:18 回复(0)
public class Main {
    static long res2;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i <n; i++){
            nums[i] = in.nextInt();
        }
        
        for(int i: nums){
            res2 = Math.max(res2, i*i);
        }
        for(int i = 0; i < n; i++){
            int j = i+1;
            int sum = nums[i];
            int k = i-1;
            while(j < n && nums[j] >= nums[i]){
                
                sum += nums[j];
                j++;
            }
            while(k >= 0 && nums[k] >= nums[i]){
                
                sum += nums[k];
                k--;
            }
            if(j <= n && k>= -1){
                res2 = Math.max(res2, sum*nums[i]);
            }

        }
        System.out.println(res2);
    }
}

发表于 2023-03-08 20:31:39 回复(0)