未排序数组中累加和为给定值的最长子数组系列问题补1

[编程题]未排序数组中累加和为给定值的最长子数组系列问题补1

热度指数：3301 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个无序数组arr，其中元素可正、可负、可0。求arr所有子数组中正数与负数个数相等的最长子数组的长度。

[要求]

时间复杂度为

，空间复杂度为

输入描述:

第一行一个整数N，表示数组长度
接下来一行有N个数表示数组中的数

输出描述:

输出一个整数表示答案

示例1

输入

5
1 -2 1 1 1

输出

备注:

算法知识视频讲解

Python

湉子1131

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

sums = 0
dic = {0:-1}
ans = 0
for i in range(N):
    if arr[i]>0:
        sums += 1
    elif arr[i]<0:
        sums -= 1
    if sums not in dic:
        dic[sums] = i
    else:
        ans = max(ans,i-dic[sums])
print(ans)

发表于 2019-10-08 20:40:39 回复(0)