Untitled

 avatar
unknown
python
2 months ago
805 B
6
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