首页 > 试题广场 >

编程题2

[编程题]编程题2
  • 热度指数:11184 时间限制: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
//复杂度O(n),应该是Leetcode 84. Largest Rectangle in Histogram 题目的变种;
//原理差不太多,有很多大神解答过,只是这里“最大矩形”的宽度变成了区间的累加和;
//除使用堆栈外,还需要一个累加和数组,方便直接查询指定区间的和。
#include<iostream>
#include<vector>
#include<stack>

using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<int> nums(n);
    vector<int> cusum(n);
    for(int i=0;i<n;i++)
        cin>>nums[i];
    cusum[0]=nums[0];
    for(int i=1;i<n;i++)
        cusum[i]=cusum[i-1]+nums[i];
    nums.push_back(0);
    stack<int> stk;
    int i=0;
    int ans=0;
    while(i<nums.size())
    {
        if(stk.empty()||nums[i]>=nums[stk.top()])
            stk.push(i++);
        else
        {
            int h=stk.top();
            stk.pop();
            int st=(stk.empty())?cusum[i-1]:(cusum[i-1]-cusum[stk.top()]);
            ans=max(ans,nums[h]*st);
        }
    }
    cout<<ans;
    return 0;
}
发表于 2018-06-26 12:29:15 回复(2)
import sys
n = int(sys.stdin.readline().strip())
value = list(map(int,sys.stdin.readline().split()))
ans = []
for i in range(1,n+1):
    ans.extend([sum(value[j:i])*min(value[j:i]) for j in range(i)])
print(max(ans))

编辑于 2018-03-27 04:28:01 回复(2)
import sys
n = int(sys.stdin.readline().strip())
p = list(map(int,sys.stdin.readline().strip().split()))

result = 0
stack = []
sumStack = []
for i in range(n):
    tempSum = p[i]
    while stack and p[i]<p[stack[-1]]:
        tempId = stack.pop()
        sumStack[-1] = sumStack[-1] + tempSum
        tempSum = sumStack.pop()
        temp = p[tempId]*(tempSum-p[i])
        if temp>result:
            result = temp
    stack.append(i)
    sumStack.append(tempSum)
    
while stack:
    tempId = stack.pop()
    sumStack[-1] = sumStack[-1] + tempSum
    tempSum = sumStack.pop()
    temp = p[tempId]*(tempSum-p[i])
    if temp>result:
        result = temp  
    
print(result)
#case:100%,不容易啊
编辑于 2019-03-23 19:12:28 回复(1)
时间复杂度为 nlogn

import java.util.Scanner;

//元素的相应位置不能变
public class Main {
    public static int max = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] num = new int[n];
        
        int sum = 0;
        int minId = 0;
        for(int i=0;i<n;i++){
            num[i] = sc.nextInt();
            sum += num[i];
            if(num[i]<num[minId])
                minId = i;
        }
        
        max = sum * num[minId];
        patition(num,0,minId,n-1);
        
        System.out.println(max);
    }
    
    //可能更大的区间为: lo~~j-1 或 j+1~~hi
    public static void patition(int[] num,int lo,int j,int hi){
        if(lo>hi || j<lo || j>hi) return;
        
        int minId = lo;
        int min = num[minId];
        int sum = num[minId];
        for(int i=lo+1;i<j;i++){
            sum += num[i];
            if(min>num[i]){
                minId = i;
                min = num[i];
            }
        }
        int m = min * sum;
        if(m>max)
            max = m;        
        patition(num,lo,minId,j-1);
        
        minId = hi;
        min = num[minId];
        sum = num[minId];
        for(int i=hi-1;i>j;i--){
            sum += num[i];
            if(min>num[i]){
                minId = i;
                min = num[i];
            }
        }
        m = min * sum;
        if(m>max)
            max = m;
        patition(num,j+1,minId,hi);
        
    }
}

发表于 2018-05-10 22:15:41 回复(0)
Java 版本

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;

//元素的相应位置不能变
public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] num = new int[n + 1];

        for (int i = 0; i < n; i++) {
            num[i] = sc.nextInt();
        }
        num[n] = 0; // append 0 to the last position

        /*
        int n = 5;
        int[] num = new int[n + 1];
        Random rand = new Random();
        for (int i = 0; i < n; i++) {
            num[i] = rand.nextInt(100) + 1;
        }
         */
        Stack<Integer> stack = new Stack<Integer>();
        Stack<Integer> sumstack = new Stack<Integer>();
        int i = 0;
        int tempsum = 0;
        int result = 0;
        while (i < num.length) {
            if (stack.size() == 0 || num[i] > stack.lastElement()) {// 如果数组的元素大于栈顶  put it into the stack

                stack.add(num[i]);
                sumstack.add(tempsum); // accumlate add
                tempsum = 0;
                i++;

            } else { // small than top ele of stack; pop out, and cal the accumate result
                int temp = stack.pop(); // the top ele
                tempsum += (temp + sumstack.pop());  // accumate add
                result = Math.max(tempsum * temp, result); // if the max one, otherwise swap

            }

        }

        System.out.println(result);
    }

}


发表于 2020-03-30 22:11:06 回复(0)
AC80%.
idea:while array != []:
          array.pop()
          find min value, Max=max(MAX,min * sum)
          将list以最小元素分成两段. array.push(new list)
自认为是最优算法.如果有改进之处还请指出,谢谢。
number = int(input())
array = list(map(int,input().split()))
 
Max = 0
stack = []
stack.append(array)
for i in range(number):
    List = stack.pop()
    Min = min(List)
    if Min != 0:
        flag = Min * sum(List)
        if flag > Max:
            Max = flag
    if List.index(Min) != 0:
        stack.append(List[:List.index(Min)])
    if List.index(Min) != len(List)-1:
        stack.append(List[List.index(Min)+1:])
print(Max)


发表于 2020-03-30 10:10:56 回复(0)
介绍一个简洁一点的分治解法,找到数组最小值,那么包含该最小值的所有数组中,整个数组那个区间最优。不包含该最小值的区间要么在该最小值的左边区间,要么在右边,分治即可。
考虑代码简洁下面代码是递归,python会爆内存,改成循环迭代应该就行。
def Find(*List):
    if len(List)==0:
        return 0
    MinPos=List.index(min(List))
    Whole=sum(List)*min(List)
    Left=Find(*List[:MinPos])
    Right=Find(*List[MinPos+1:])
    return max(Whole,Left,Right)
 
n=int(input())
num=[]
t=input().split(' ')
for i in range(n):
    num.append(int(t[i]))
print(Find(*num))



编辑于 2020-03-18 11:02:48 回复(1)
裸的单调栈
发表于 2019-08-09 10:17:17 回复(0)
完美AC。以第i个元素为最小值分别向两边扩大区间至最大,算出该元素与区间内所有数的和的
乘积f(i),遍历所有元素,更新f(i)即可。
#include <iostream>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        int x[n];
        for (int i=0; i<n; i++)
            cin>>x[i];
        int max=0;
        for (int i=0; i<n; i++)
        {
            int j=i;
            int k=i-1;
            int sum1=0;
            while(x[i]<=x[j] && j<n)
            {
                sum1+=x[j];
                j++;
            }
            while(x[i]<=x[k] && k>=0)
            {
                sum1+=x[k];
                k--;
            }
            int temp=sum1;
            if (x[i]*temp>max)
                max=x[i]*temp;

        }
        cout << max << endl;
    }
    return 0;
}

发表于 2018-03-22 16:38:37 回复(9)

时间复杂度为O(n)算法:
对序列维护一个单调非减的栈。遍历输入数组,当栈不为空且栈顶元素大于当前的值时,栈顶出栈,并记录现在还留在栈中但需要出栈总和(pop_sum),还要记录在出栈元素之前出栈的总和,用stack_pop_before来记录栈中每个元素在加入栈前需要出栈的总和,也就是说,因为栈中的某些元素在加入栈前需要让其前面的一些元素出栈,而后面的结果计算需要用这部分已经出栈的元素,故要增加一个辅助的栈记录。

n=int(raw_input())
arr=[int(x) for x in raw_input()[:-1].split(' ')]

arr.append(-1)
i=0
stack_pop_before=[]
stack=[]
ans=0
while i<=n:
    num=arr[i]
    pop_sum=0
    pop_before=0
    while stack and num<stack[-1]:
        pop_num=stack.pop()
        pop_sum+=pop_num
        pop_before+=stack_pop_before.pop()
        ans=max(ans,(pop_before+pop_sum)*pop_num)
    stack_pop_before.append(pop_before+pop_sum)
    stack.append(num)
    i+=1
print ans

编辑于 2018-02-17 15:37:15 回复(8)
n=int(input())
arr=[int(x) for x in input().split()]
stack = []
arr.append(0)
result = 0
i = 0
presum = []
tempsum = 0
while i<len(arr):
    if not stack or arr[i]>=stack[-1]:
        presum.append(tempsum)
        tempsum = 0
        stack.append(arr[i])
        i+=1
    else:
        temp = stack.pop(-1)
        tempsum+=(temp+presum.pop())
        result = max(tempsum*temp,result)
print(result)
发表于 2019-02-10 15:00:01 回复(1)
用栈,用哨兵,找出最小值,和包含此最小值的最长区间,最小值乘求和更新就可以了。
def maxnum(nums):
    stack = []
    maxpro = 0
    for i, num in enumerate(nums):
        while stack and num < nums[stack[-1]]:
            cur = stack.pop()
            maxpro = max(maxpro, nums[cur] * sum(nums[stack[-1] + 1 : i]))
        stack.append(i)
    return maxpro
n = int(input())
nums = [0] + list(map(int, input().split())) + [0]
print(maxnum(nums))



发表于 2020-03-27 18:47:30 回复(0)
//LeetCode84题的变种,主要思路是以每个数作为最小值,找到它的左边界和右边界,然后最小值乘以边界的累加和;如果是遍历每个值找其左右边界,会超时(应该只能ac70%左右);使用压栈的方法可以使得递增的序列不用重复计算其左右边界(最终用时136ms);
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int main()
{
    int n,t,largest=0;
    cin>>n;
    vector<int> data(n);
    data.push_back(0);
    vector<int> cosum(n);
    stack<int> stk;
    for (int i=0;i<n;++i){
        cin>>t;
        data[i]=t;
        if (i==0) cosum[i]=t;
        else cosum[i]=cosum[i-1]+t;
    }
    for (int i=0;i<n;++i){
        if (stk.empty() || data[i]>=data[stk.top()])
            stk.push(i);
        else {
            int right=stk.top();
            stk.pop();
            int Sum=stk.empty()?cosum[i-1]:cosum[i-1]-cosum[stk.top()];
            largest=max(largest,Sum*data[right]);
            --i;
        }
    }
    cout<<largest<<endl;
}


发表于 2018-08-28 12:07:26 回复(2)
import sys
for n in sys.stdin:
    # n = input()
    if len(n) <= 0:
        break
    n = int(n.strip())

    nums = input().strip().split(" ")
    nums = [-1] + [int(x) for x in nums] + [-1]
    pre_sum = [0]
    for x in nums:
        pre_sum.append(pre_sum[-1] + x)
    pre_sum = pre_sum[1:]

    left = [0] * len(nums)
    right = [len(nums) - 1] * len(nums)
    stack = []
    for i, x in enumerate(nums):
        while len(stack) > 1 and x <= stack[-1][1]:
            tmp = stack.pop(-1)
            left[tmp[0]] = stack[-1][0] + 1
        else:
            stack.append((i, x))
    stack = []
    for i in range(len(nums) - 1, -1, -1):
        x = nums[i]
        while len(stack) > 1 and x <= stack[-1][1]:
            tmp = stack.pop(-1)
            right[tmp[0]] = stack[-1][0] - 1
        else:
            stack.append((i, x))
    res = 0
    for i in range(1, len(nums) - 1):
        res = max(res, nums[i] * (nums[left[i]] + pre_sum[right[i]] - pre_sum[left[i]]))
    # print(left,right)
    print(res)
100% AC 代码
虽然看起来很长,但是实际上比其他人的好理解的多(因为存在复用代码),总的来说跟我写过的一道力扣题很像,不过我的做法和他们的很不一样,我是设置了一个left和right数组用来存他们各自的左右边界(因为这道题我是想通过找到每个数的左右边界来做)
① 对于数组nums来说,只要找到了所有元素的最长区间(最大和),就能够求出x*最长区间和,然后维护答案res。
② 那么怎么去求边界呢? 实际上,可以利用单调栈,我只要有一个只允许严格单调递增的栈(不存在等于),那么我就能找到所有元素的左边界:这是因为出栈的时候都是从大到小出---毕竟是严格单调撒,所以出了一个元素x,这个时候栈顶y就是出来元素x的左边界了。
③ 那么右边界怎么求? 答案是左边界怎么求,右边界就模仿这个过程,所以最开始说复用了代码,理解起来是不困难的,一旦理解,代码就不觉得长了。
④ 最后怎么维护答案res? 最开始记得求一个前缀和,然后利用left和right数组找到最大区间就可以成功维护答案res了。
发表于 2023-08-25 19:48:37 回复(0)
Fyuuuy
编辑于 2023-03-29 01:21:26 回复(0)
def ans(nums):
    stack = [0]
    nums = [0] + nums + [0] # 添加哨兵,保证栈里面所有的元素都可以出栈
    n = len(nums)
    res = 0
   # 利用 单调栈 找到以每个元素为区间最小元素的最长区间
    for i in range(1,n):
        while stack and nums[i] < nums[stack[-1]]:
            min_num = nums[stack.pop()] # 区间的最小值
            sum_num = sum(nums[stack[-1]+1:i]) #区间和
            res =max(res,min_num*sum_num) # 结果
        stack.append(i)
    print(res)
if __name__ == "__main__":
    n = int(input())
    num = list(map(int,input().split()))
    ans(num)

        

        

发表于 2022-08-08 17:37:41 回复(0)
有一个没通过,大佬能帮忙看下那里的问题吗
#include <stdio.h>
#include <stdio.h>
 
 
int main()
{
    int num = 0;
    unsigned int array[500000] = {0};
    scanf("%d",&num);
    for(int i =0; i < num; i++)
    {
        scanf("%d",&array[i]);
    }
    int max = 0;
    unsigned long long sum = 0;
     
    for(int i =0; i < num; i++)
    {
        sum = array[i];
        if(i == num-1 ||array[i]<=array[i+1] && array[i]<=array[i-1] )
        {
            for(int j = i-1; j>=0;j--)
            {
                if(array[j] < array[i])
                {
                    break;
                }
                sum += array[j];
            }
            max = (array[i]*sum > max)?(array[i]*sum):max;
        }
        if(i ==0 || array[i]<=array[i+1] && array[i]<=array[i-1])
        {
            for(int j = i+1; j < num ;j++)
            {
                if(array[j] < array[i])
                {
                    break;
                }
                sum += array[j];
            }
            
        }
         max = (array[i]*sum > max)?(array[i]*sum):max;
    }
 
    printf("%llu\n",max);
     
     
     
    return 0;
}

发表于 2022-06-25 00:35:13 回复(0)
求问各位大佬,为什么这个例子的结果是 16685 ?
我用计算器算了一下,这个数是由 47 * (25 + 47 + 56 + 59 + 81 + 87) 得到的。
这样的话,为什么区间最小的数不是 25 ?
编辑于 2022-03-30 21:25:01 回复(0)

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>

int function(vector<int>& data, int x) {
    int sum = 0;
    //先加左边
    int left = x;
    while (left >= 0) {
        if (data[left]<data[x]) {
            break;
        }
        sum = sum + data[left];
        left--;
    }
    int right = x + 1;
    while (right <= data.size() - 1) {
        if (data[right]<data[x]) {
            break;
        }
        sum = sum + data[right];
        right++;
    }
    return data[x] * sum;
}

int main() {
    int n;
    cin >> n;
    vector<int> data;
    int x;
    for (int i = 0; i<n; i++) {
        scanf("%d", &x);
        data.push_back(x);
    }
    int res = 0;
    for (int i = 0; i<n; i++) {
        res = max(res, function(data, i));
        //cout<<max(res,function(data,i))<<endl;
    }
    cout << res << endl;
    return 0;
}
发表于 2022-03-29 14:56:17 回复(0)
from itertools import accumulate

n = int(input())
heights = [0] + list(map(int, input().strip().split(' '))) + [0]
left, right = [0] * (n + 2), [0] * (n + 2)

mono_stack = list()
for i in range(n + 2):
    while mono_stack and heights[mono_stack[-1]] >= heights[i]:
        mono_stack.pop()
    left[i] = mono_stack[-1] if mono_stack else -1
    mono_stack.append(i)

mono_stack = list()
for i in range(n + 1, -1, -1):
    while mono_stack and heights[mono_stack[-1]] >= heights[i]:
        mono_stack.pop()
    right[i] = mono_stack[-1] if mono_stack else n + 2
    mono_stack.append(i)

acc = list(accumulate(heights))
ans = max((acc[right[i] - 1] - acc[left[i]]) * heights[i] for i in range(1, n + 1))
print(ans)

AC, 运行时间: 842 ms 占用内存:57340K.  模仿力扣84题
发表于 2022-02-28 11:16:42 回复(0)