编程题2

[编程题]编程题2

热度指数：11192 时间限制：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

输出

算法知识视频讲解

Python

zhq1999

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)

Python

吴永泰

 def fun(nums):
    if not nums or len(nums) < 1:
        return 0
    dp = [0 for i in range(len(nums))]
    for i in range(len(nums)):
        dp[i] = helper(nums, i, i, i)
    return max(dp)


def helper(nums, index, l, r):
    while 0 <= l and nums[l] >= nums[index]:
        l -= 1
    while r < len(nums) and nums[r] >= nums[index]:
        r += 1
    value = nums[index] * sum(nums[l+1:r])
    return value


if __name__=='__main__':
    nums = [6,2,1]
    res = fun(nums)
    print(res)

请问各位大佬这个代码错在哪里？

发表于 2019-09-20 20:31:45 回复(0)

Python

a1ca4b

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)

Python

牛客8046156号

#解析请看https://blog.csdn.net/weixin_42001089/article/details/84203651第二部分

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)

Python

麻瓜工程师

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)