Given an array arr[] of integers of size N and a number X, the task is to find the sum of subarray having maximum sum less than or equal to the given value of X.
Example 1:
Input: N = 5, X = 11
arr[] = {1, 2, 3, 4, 5} 
Output:  10
Explanation: Subarray having maximum 
sum is {1, 2, 3, 4}.
 
Example 2:
Input: N = 5, X = 7
arr[] = {2, 4, 6, 8, 10} 
Output:  6
Explanation: Subarray having maximum 
sum is {2, 4} or {6}.
 
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function calculateMaxSumLength() that takes array arr, integer N, and integer X as parameters and returns maximum sum of any subarray that is less than or equal to x.
 
Expected Time Complexity: O(N). 
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ arr[i] ≤ 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Amortized analysis

Starter code: class Solution:

    def findMaxSubarraySum(self, arr, n, k):

        # Your code goes here

Solutions:
class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		sum = 0
		ans = 0
		(i, j) = (0, 0)
		while j < n:
			sum += arr[j]
			if sum < k:
				ans = max(ans, sum)
				j += 1
			elif sum == k:
				return k
			else:
				while sum > k:
					sum -= arr[i]
					i += 1
				ans = max(ans, sum)
				j += 1
		return ans


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		max1 = 0
		s = 0
		i = 0
		j = 0
		while i < n:
			s += arr[i]
			if s > k:
				while s > k:
					s -= arr[j]
					j += 1
			max1 = max(max1, s)
			i += 1
		max1 = max(max1, s)
		return max1


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		(ans, cur) = (0, 0)
		(fp, sp) = (0, 0)
		while sp < n:
			if cur <= k:
				cur += arr[sp]
			while cur > k and fp <= sp:
				cur -= arr[fp]
				fp += 1
			sp += 1
			ans = max(ans, cur)
		return ans


import math

class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		maxi = -math.inf
		fsum = 0
		left = 0
		for i in range(n):
			fsum += arr[i]
			while fsum > k:
				fsum -= arr[left]
				left += 1
			maxi = max(maxi, fsum)
		return maxi


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		left = 0
		maxi = 0
		su = 0
		for right in range(0, n):
			su += arr[right]
			while su > k:
				su -= arr[left]
				left += 1
			maxi = max(maxi, su)
		return maxi


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		maxSum = 0
		(head, tail) = (0, 0)
		maxVal = -1
		while tail < n:
			maxSum += arr[tail]
			if maxSum == k:
				return k
			elif maxSum > k:
				while head <= tail:
					maxSum -= arr[head]
					head = head + 1
					if maxSum == k:
						return k
					elif maxSum < k:
						maxVal = max(maxVal, maxSum)
						break
			else:
				maxVal = max(maxVal, maxSum)
			tail += 1
		return maxVal


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		max_sum = float('-inf')
		curr_sum = 0
		i = 0
		j = 0
		while j < n:
			curr_sum += arr[j]
			if curr_sum <= k:
				max_sum = max(max_sum, curr_sum)
			else:
				while curr_sum > k:
					curr_sum -= arr[i]
					if curr_sum <= k:
						max_sum = max(max_sum, curr_sum)
					i += 1
			j += 1
		return max_sum


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		maxi = float('-inf')
		i = 0
		j = 0
		pre = 0
		while i < n:
			pre += arr[i]
			if pre <= k:
				maxi = max(pre, maxi)
			else:
				while pre > k and j <= i:
					pre -= arr[j]
					j += 1
				if pre <= k:
					maxi = max(maxi, pre)
			i += 1
		return maxi


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		maxi = 0
		total = arr[0]
		(start, end) = (0, 0)
		while start < n and end < n:
			if total <= k:
				maxi = max(maxi, total)
				end += 1
				if end < n:
					total += arr[end]
			else:
				total -= arr[start]
				start += 1
		return maxi


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		subasum = arr[0]
		sum = 0
		for i in range(0, n):
			subasum = arr[i]
			if subasum < k:
				sum = max(subasum, sum)
			elif subasum == k:
				return subasum
			for j in range(i + 1, n):
				subasum = subasum + arr[j]
				if subasum < k:
					sum = max(subasum, sum)
				elif subasum == k:
					return subasum
				elif subasum > k:
					break
		return sum


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		i = 0
		j = 0
		summ = 0
		maxi = -1000000007
		while i < n:
			summ += arr[i]
			if summ <= k:
				maxi = max(maxi, summ)
			else:
				while summ > k and j <= i:
					summ -= arr[j]
					j += 1
				if summ <= k:
					maxi = max(maxi, summ)
			i += 1
		return maxi


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		maxi = 0
		summa = 0
		j = 0
		for item in arr:
			while j < n and summa + arr[j] <= k:
				summa += arr[j]
				maxi = max(maxi, summa)
				j += 1
			summa -= item
		return maxi


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		left = 0
		s = 0
		m = 0
		for right in range(n):
			s += arr[right]
			if s <= k:
				m = max(s, m)
			else:
				while s > k and left <= right:
					s -= arr[left]
					left += 1
				if s <= k:
					m = max(m, s)
		return m


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		a = -1
		sum = 0
		s = 0
		for i in range(n):
			sum += arr[i]
			while sum > k:
				sum -= arr[s]
				s = s + 1
			else:
				a = max(a, sum)
		return a


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		i = 0
		j = 0
		sumi = 0
		maxi = 0
		while j < len(arr):
			sumi = sumi + arr[j]
			if sumi <= k:
				maxi = max(maxi, sumi)
			while sumi > k:
				sumi = sumi - arr[i]
				if sumi <= k:
					maxi = max(maxi, sumi)
				i = i + 1
			j = j + 1
		return maxi


class Solution:

	def findMaxSubarraySum(self, a, n, x):
		for i in a:
			assert i > 0 and i <= 10 ** 4
		if sum(a) <= x:
			return sum(a)
		total = 0
		ans = -1
		start = 0
		for i in range(n + 1):
			while total > x and start < i - 1:
				total -= a[start]
				start += 1
			if total < x:
				ans = max(ans, total)
			elif total == x:
				return x
			if i < n:
				total += a[i]
		return ans


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		l = r = 0
		ma = 0
		cu = arr[0]
		while r < n:
			if cu <= k:
				ma = max(ma, cu)
				r += 1
				if r < n:
					cu += arr[r]
			if cu > k:
				cu -= arr[l]
				l += 1
		return ma


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		res = float('-inf')
		s = 0
		j = 0
		for i in range(n):
			s += arr[i]
			if s > k:
				while j <= i and s > k:
					s -= arr[j]
					j += 1
			if s <= k:
				res = max(res, s)
				if res == k:
					return k
		if res != float('-inf'):
			return res
		return -1


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		i = 0
		sums = 0
		maxi = 0
		for j in range(n):
			sums += arr[j]
			if sums <= k:
				maxi = max(maxi, sums)
			while sums > k:
				sums -= arr[i]
				i += 1
				if sums <= k:
					maxi = max(maxi, sums)
		return maxi


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		start = 0
		tot = 0
		res = 0
		for end in range(n):
			tot += arr[end]
			while tot > k:
				tot -= arr[start]
				start += 1
			res = max(res, tot)
		return res


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		currSum = 0
		start = 0
		maxSum = 0
		for i in range(n):
			currSum += arr[i]
			while currSum > k:
				currSum -= arr[start]
				start += 1
			maxSum = max(maxSum, currSum)
		return maxSum


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		sumi = 0
		res = 0
		j = 0
		for i in range(n):
			sumi += arr[i]
			while k < sumi:
				sumi -= arr[j]
				j += 1
			if sumi <= k:
				res = max(res, sumi)
		return res


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		c = 0
		s = 0
		res = 0
		for i in range(n):
			s = s + arr[i]
			while s > k:
				s = s - arr[c]
				c = c + 1
			res = max(s, res)
		return res


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		ws = 0
		we = 0
		res = 0
		sumi = 0
		for we in range(n):
			sumi += arr[we]
			while sumi > k:
				sumi -= arr[ws]
				ws += 1
			if sumi <= k:
				res = max(res, sumi)
		return res


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		i = 0
		j = 1
		currSum = arr[0]
		maxSum = 0
		while i <= j and j < n:
			if currSum <= k:
				maxSum = max(maxSum, currSum)
			while currSum + arr[j] > k and i < j:
				currSum -= arr[i]
				i += 1
			currSum += arr[j]
			j += 1
		if currSum <= k:
			maxSum = max(maxSum, currSum)
		return maxSum


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		currsum = arr[0]
		start = 0
		maxsum = 0
		if n == 1:
			if arr[0] <= k:
				return arr[0]
			else:
				return 0
		for i in range(1, n):
			if currsum <= k:
				maxsum = max(maxsum, currsum)
			while currsum + arr[i] > k and start < i:
				currsum = currsum - arr[start]
				start = start + 1
			currsum = currsum + arr[i]
			if currsum <= k:
				maxsum = max(maxsum, currsum)
		return maxsum


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		j = 0
		Maxlen = 0
		Sum = 0
		for i in range(n):
			Sum += arr[i]
			while Sum > k:
				Sum -= arr[j]
				j += 1
			Maxlen = max(Sum, Maxlen)
		return Maxlen


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		ans = 0
		sm = 0
		s = 0
		for e in range(n):
			sm += arr[e]
			while sm > k and s < e:
				sm -= arr[s]
				s += 1
			if sm <= k:
				ans = max(ans, sm)
		return ans


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		ans = 0
		s = 0
		j = 0
		for i in range(n):
			s += arr[i]
			while s > k:
				s -= arr[j]
				j += 1
			ans = max(ans, s)
		return ans


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		start = 0
		total = 0
		curr_sum = 0
		for i in range(n):
			if curr_sum <= k:
				total = max(total, curr_sum)
			while curr_sum + arr[i] > k and start < i:
				curr_sum -= arr[start]
				start += 1
			curr_sum += arr[i]
		if curr_sum <= k:
			total = max(total, curr_sum)
		return total


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		if k in arr:
			return k
		(maxx, summ) = (0, 0)
		j = 0
		for i in range(n):
			summ += arr[i]
			if summ > k:
				while summ > k:
					summ -= arr[j]
					j += 1
			if summ <= k:
				maxx = max(summ, maxx)
		return maxx


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		l = 0
		sum1 = 0
		maxi = 0
		for r in range(n):
			sum1 += arr[r]
			while sum1 > k:
				maxi = max(maxi, sum(arr[l:r]))
				sum1 -= arr[l]
				l += 1
		maxi = max(maxi, sum1)
		return maxi


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		i = 0
		j = 0
		s = 0
		d = -999999999
		while j < n:
			s += arr[j]
			if s <= k and s > d:
				d = s
			while s > k:
				s = s - arr[i]
				i += 1
			if s <= k and s > d:
				d = s
			j += 1
		return d


import sys

class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		(start, end, curr_sum, max_sum) = (0, 0, 0, -sys.maxsize)
		while end < n:
			curr_sum = curr_sum + arr[end]
			while start <= end and curr_sum > k:
				curr_sum = curr_sum - arr[start]
				start = start + 1
			max_sum = max(curr_sum, max_sum)
			end = end + 1
		return max_sum


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		count = 0
		ans = -1 << 32
		left = right = cur = 0
		while right < n:
			cur += arr[right]
			while cur > k:
				cur -= arr[left]
				left += 1
			ans = max(ans, cur)
			right += 1
		return ans


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		i = 0
		j = 0
		mx = float('-inf')
		sum = 0
		while j < n:
			sum += arr[j]
			while sum > k:
				sum -= arr[i]
				i += 1
			mx = max(sum, mx)
			j += 1
		return mx


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		curr_sum = 0
		max_sum = -12345678
		start = 0
		for i in range(n):
			curr_sum += arr[i]
			while curr_sum > k:
				curr_sum = curr_sum - arr[start]
				start += 1
			max_sum = max(max_sum, curr_sum)
		return max_sum


class Solution:

	def findMaxSubarraySum(self, C, n, B):
		sum = 0
		ans = 0
		start = 0
		end = 0
		while end < len(C):
			sum += C[end]
			if sum <= B:
				ans = max(ans, sum)
			elif sum > B:
				while sum > B:
					sum = sum - C[start]
					start += 1
				ans = max(ans, sum)
			end += 1
		return ans


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		currsum = 0
		maxSum = 0
		(i, j) = (0, 0)
		while j < len(arr):
			currsum += arr[j]
			if currsum > k:
				while currsum > k:
					currsum -= arr[i]
					i += 1
			maxSum = max(maxSum, currsum)
			j += 1
		return maxSum


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		start = 0
		s = 0
		end = 0
		a = []
		for end in range(n):
			s = s + arr[end]
			while s > k:
				s = s - arr[start]
				start = start + 1
			else:
				a.append(s)
		a.sort()
		return a[-1]


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		(i, j) = (0, 0)
		res = 0
		summ = 0
		while j < n:
			summ += arr[j]
			while i <= j and summ > k:
				summ -= arr[i]
				i += 1
			res = max(res, summ)
			j += 1
		return res


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		curr = arr[0]
		maxx = 0
		start = 0
		for i in range(1, n):
			if curr <= k:
				maxx = max(curr, maxx)
			while curr + arr[i] > k and start < i:
				curr -= arr[start]
				start += 1
			curr += arr[i]
		if curr <= k:
			maxx = max(curr, maxx)
		return maxx


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		currSum = 0
		ws = 0
		maxSum = 0
		for we in range(n):
			currSum += arr[we]
			while currSum > k and ws <= we:
				currSum -= arr[ws]
				ws += 1
			if currSum > maxSum and currSum <= k:
				maxSum = currSum
		return maxSum


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		currentRunningSum = 0
		windowStart = 0
		maxSum = float('-inf')
		for windowEnd in range(n):
			currentRunningSum += arr[windowEnd]
			while currentRunningSum > k:
				currentRunningSum -= arr[windowStart]
				windowStart += 1
			maxSum = max(maxSum, currentRunningSum)
		return maxSum
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		a = list(map(int, input().split()))
		k = int(input())
		ob = Solution()
		ans = ob.findMaxSubarraySum(a, n, k)
		print(ans)


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		i = 0
		j = 0
		mx = 0
		s = 0
		while i < n:
			s += arr[i]
			while s > k and j < i:
				s -= arr[j]
				j += 1
			if s <= k:
				mx = max(s, mx)
			i += 1
		return mx
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		a = list(map(int, input().split()))
		k = int(input())
		ob = Solution()
		ans = ob.findMaxSubarraySum(a, n, k)
		print(ans)


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		(p, q) = (-1, -1)
		total = 0
		ans = float('-inf')
		while True:
			if total <= k:
				ans = max(ans, total)
			if total < k:
				q += 1
				if q == n:
					break
				total += arr[q]
			else:
				p += 1
				total -= arr[p]
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		a = list(map(int, input().split()))
		k = int(input())
		ob = Solution()
		ans = ob.findMaxSubarraySum(a, n, k)
		print(ans)


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		res = currSum = 0
		start = 0
		for i in range(n):
			currSum += arr[i]
			while currSum > k and start <= i:
				currSum -= arr[start]
				start += 1
			if currSum <= k:
				res = max(res, currSum)
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		a = list(map(int, input().split()))
		k = int(input())
		ob = Solution()
		ans = ob.findMaxSubarraySum(a, n, k)
		print(ans)


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		i = 0
		j = 0
		sum1 = 0
		maxi = 0
		while j < n:
			sum1 = sum1 + arr[j]
			if sum1 <= k:
				maxi = max(maxi, sum1)
				j = j + 1
			elif sum1 > k:
				while sum1 > k:
					sum1 = sum1 - arr[i]
					i = i + 1
					if sum1 <= k:
						maxi = max(maxi, sum1)
				j = j + 1
		return maxi
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		a = list(map(int, input().split()))
		k = int(input())
		ob = Solution()
		ans = ob.findMaxSubarraySum(a, n, k)
		print(ans)


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		headPointer = 0
		tailPointer = 0
		maxSum = 0
		currSum = 0
		while tailPointer < n:
			currSum += arr[tailPointer]
			if currSum > k:
				while currSum > k:
					currSum -= arr[headPointer]
					headPointer += 1
			maxSum = max(maxSum, currSum)
			tailPointer += 1
		return maxSum
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		a = list(map(int, input().split()))
		k = int(input())
		ob = Solution()
		ans = ob.findMaxSubarraySum(a, n, k)
		print(ans)


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		maxsum = 0
		cursum = arr[0]
		start = 0
		end = 1
		while end < n:
			if cursum <= k:
				maxsum = max(cursum, maxsum)
			while cursum + arr[end] > k and start < end:
				cursum -= arr[start]
				start += 1
			cursum += arr[end]
			end += 1
		if cursum <= k:
			maxsum = max(maxsum, cursum)
		return maxsum
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		a = list(map(int, input().split()))
		k = int(input())
		ob = Solution()
		ans = ob.findMaxSubarraySum(a, n, k)
		print(ans)


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		i = j = 0
		total = 0
		max_sum = 0
		while j < n:
			total += arr[j]
			if total <= k:
				max_sum = max(total, max_sum)
				j += 1
			else:
				while total > k:
					total -= arr[i]
					i += 1
				if total <= k:
					max_sum = max(total, max_sum)
				j += 1
		return max_sum
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		a = list(map(int, input().split()))
		k = int(input())
		ob = Solution()
		ans = ob.findMaxSubarraySum(a, n, k)
		print(ans)


class Solution:

	def findMaxSubarraySum(self, arr, n, x):
		_max = i = tot = start = 0
		while i < n:
			tot += arr[i]
			if tot <= x:
				_max = max(_max, tot)
			else:
				while tot > x:
					tot -= arr[start]
					start += 1
				_max = max(_max, tot)
			i += 1
		return _max
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		a = list(map(int, input().split()))
		k = int(input())
		ob = Solution()
		ans = ob.findMaxSubarraySum(a, n, k)
		print(ans)


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		s = 0
		mx = min(arr)
		i = 0
		j = 0
		while j < len(arr):
			s += arr[j]
			while s > k:
				s -= arr[i]
				i += 1
			mx = max(s, mx)
			j += 1
		if mx > k:
			return 0
		return mx


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		i = 0
		j = 0
		Sum = 0
		mx = 0
		while j < n:
			Sum = Sum + arr[j]
			if Sum <= k:
				j = j + 1
				mx = max(mx, Sum)
			elif Sum > k:
				while Sum > k:
					Sum = Sum - arr[i]
					i = i + 1
					if Sum <= k:
						mx = max(mx, Sum)
				j = j + 1
		return mx


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		i = 0
		j = 0
		maxsum = 0
		tempsum = 0
		while j != n:
			tempsum += arr[j]
			j += 1
			while tempsum > k:
				tempsum -= arr[i]
				i += 1
			maxsum = max(maxsum, tempsum)
		return maxsum


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		startIndex = 0
		currentSum = 0
		maxSum = 0
		for endIndex in range(0, n):
			if currentSum <= k:
				maxSum = max(maxSum, currentSum)
			while currentSum + arr[endIndex] > k and startIndex < n:
				currentSum -= arr[startIndex]
				startIndex += 1
			currentSum += arr[endIndex]
		if currentSum <= k:
			maxSum = max(maxSum, currentSum)
		return maxSum


class Solution:

	def findMaxSubarraySum(self, arr, n, sum):
		curr_sum = arr[0]
		max_sum = 0
		start = 0
		for i in range(1, n):
			if curr_sum <= sum:
				max_sum = max(max_sum, curr_sum)
			while curr_sum + arr[i] > sum and start < i:
				curr_sum -= arr[start]
				start += 1
			curr_sum += arr[i]
		if curr_sum <= sum:
			max_sum = max(max_sum, curr_sum)
		return max_sum


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		maxi = 0
		a = []
		currentsum = 0
		index = 0
		while index < n:
			currentsum += arr[index]
			a.append(arr[index])
			if currentsum <= k:
				maxi = max(maxi, currentsum)
			else:
				while currentsum > k:
					if len(a) == 0:
						break
					currentsum -= a[0]
					a.pop(0)
				maxi = max(maxi, currentsum)
			index += 1
		return maxi


class Solution:

	def findMaxSubarraySum(self, a, n, k):
		i = 0
		j = 0
		sa = 0
		ma = float('-inf')
		while j < n:
			sa += a[j]
			if sa <= k:
				ma = max(ma, sa)
			elif sa > k:
				while sa > k:
					sa -= a[i]
					i += 1
				if sa <= k:
					ma = max(ma, sa)
			j += 1
		return ma


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		right = 0
		left = -1
		add = 0
		max_val = 0
		while right < n:
			if add + arr[right] < k:
				add += arr[right]
				max_val = max(max_val, add)
				right += 1
			elif add + arr[right] == k:
				return k
			else:
				left += 1
				right = left
				add = 0
		return max_val


class Solution:

	def findMaxSubarraySum(self, arr, n, x):
		slow = 0
		fast = 0
		total = 0
		maxer = 0
		while fast < len(arr):
			total += arr[fast]
			if total <= x:
				maxer = max(maxer, total)
			elif total > x:
				while total > x:
					total -= arr[slow]
					slow += 1
				if total <= x:
					maxer = max(maxer, total)
			fast += 1
		return maxer


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		(cur_sum, max_sum) = (0, -10 ** 9)
		l = 0
		for i in range(n):
			cur_sum += arr[i]
			while l <= i and cur_sum > k:
				cur_sum -= arr[l]
				l += 1
			max_sum = max(max_sum, cur_sum)
		return max_sum


class Solution:

	def findMaxSubarraySum(self, arr, n, k):
		for i in range(1, n):
			arr[i] = arr[i - 1] + arr[i]
		x = 0
		y = 0
		max_val = -9223372036854775806
		while x < n:
			if arr[x] <= k:
				max_val = max(max_val, arr[x])
			else:
				while arr[x] - arr[y] > k and x > y:
					y += 1
				max_val = max(max_val, arr[x] - arr[y])
			x += 1
			if max_val == k:
				return k
		return max_val