选区间

[编程题]选区间

热度指数：3939 时间限制：C/C++ 2秒，其他语言4秒空间限制：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]的范围内;

输入描述:

第一行输入数组序列个数，第二行输入数组序列。

输出描述:

输出数组经过计算后的最大值。

示例1

输入

3
6 2 1

输出

备注:

1 ≤ n ≤ 500000

算法知识视频讲解

Python

强人锁篮

方案一（68.5%通过）：选择固定的最小值，计算不同范围的累积值相乘得到的最大值

方案二（100%通过）：基于单调栈O(n)式地计算最大值

方案一（68.5%通过）

N = int(input())
arr = list(map(int, input().split()))

ans = 0
left = min(arr)
right = max(arr) + 1
for i in range(left, right):
    minimum = i
    accumulation = 0
    for n in arr:
        if n >= minimum:
            accumulation += n
        else:
            accumulation = 0
        ans = max(ans, minimum*accumulation)
print(ans)

方案二（100%通过）

N = int(input())
arr = list(map(int, input().split())) + [0]

ans = 0
id_stack = []
integral_arr = [0]
for i,n in enumerate(arr):
    while len(id_stack) and n < arr[id_stack[-1]]:
        idx = id_stack.pop()
        minimum = arr[idx]
        accumulation = integral_arr[i] if not id_stack else integral_arr[i] - integral_arr[id_stack[-1]+1]
        ans = max(ans, minimum * accumulation)
        
    id_stack.append(i)
    integral_arr.append(integral_arr[-1] + n)
    
print(ans)

编辑于 2020-12-27 18:05:53 回复(0)

Python

编辑资料中

#python利用单调栈做需要边缘处理所以在数组后多加一个0，且因为需要计算区间和所以又开了一个数组来记录防止超时

n = int(input())

heights = list(map(int, input().split(" ")))
if n == 0:
print(0)
heights.append(0)
#单调栈做
stack, maxarea, pre_num = [], 0, [0]
for i in range(len(heights)):
while stack and heights[i] < heights[stack[-1]]:
right = stack.pop()
maxarea = max(maxarea, heights[right] * (pre_num[i] if not stack else (pre_num[i] - pre_num[stack[-1]+1])))
pre_num.append(heights[i] + pre_num[-1])
stack.append(i)
print(maxarea)

发表于 2019-07-02 20:38:53 回复(0)