Untitled
unknown
python
a month ago
805 B
5
Indexable
n = int(input())
k = int(input())
arr = []
for i in range(n):
arr.append(int(input()))
print(arr)
def brute_force(arr,k):
maxlen = 0
for i in range(len(arr)):
cs = 0
for j in range(i,len(arr)):
cs = cs + arr[j]
if cs == k and j - i + 1 > maxlen:
maxlen = j - i + 1
return maxlen
from collections import defaultdict
def optimal_solve(arr,k):
n = len(arr)
mp = defaultdict(int)
ps = 0
mp[0] = 1
maxlen = 0
for i in range(len(arr)):
ps = ps + arr[i]
x = ps - k
if x in mp:
d = i - mp[x]
if d > maxlen:
maxlen = d
else:
mp[ps] = i
return maxlen
print(optimal_solve(arr,k))Editor is loading...
Leave a Comment