Given an array arr[] of N elements, the task is to find the maximum sum of lengths of all non-overlapping subarrays with K as the maximum element in the subarray.
Example 1:
Input: N = 9, K = 4
arr[] = {2, 1, 4, 9, 2, 3, 8, 3, 4} 
Output: 5
Explanation: {2, 1, 4} => Length = 3
             {3, 4} => Length = 2
             So, 3 + 2 = 5 is the answer.
Example 2:
Input: N = 7, K = 4
arr[] = {1, 2, 3, 2, 3, 4, 1} 
Output:  7
Explanation: {1, 2, 3, 2, 3, 4, 1} 
             => Length = 7.
 
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 K as parameters and returns the sum of the length of all such subarrays.
 
Expected Time Complexity: O(N). 
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3




def calculateMaxSumLength(arr,N,K):
class Solution:
    def calculateMaxSumLength(self, arr, n, k):
        # Your code goes here

Solutions:
class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		i = 0
		ans = 0
		while i < n:
			flag = False
			count = 0
			while i < n and arr[i] <= k:
				count += 1
				if arr[i] == k:
					flag = True
				i += 1
			if flag:
				ans += count
			while i < n and arr[i] > k:
				i += 1
		return ans


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		s = 0
		cur = 0
		flag = False
		for i in range(n):
			if arr[i] > k:
				if flag:
					s += cur
				cur = 0
				flag = False
			else:
				cur += 1
				if arr[i] == k:
					flag = True
		if flag:
			s += cur
		return s


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		prv = 0
		ans = 0
		mx = 0
		for i in range(n):
			if arr[i] > k:
				if mx == k:
					ans = ans + (i - prv)
				mx = 0
				prv = i + 1
			else:
				mx = max(mx, arr[i])
				if i == len(arr) - 1 and mx == k:
					ans = ans + (i - prv + 1)
		return ans


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		c = 0
		s = 0
		flag = 0
		for i in range(n):
			if arr[i] < k:
				c += 1
			elif arr[i] == k:
				if flag == 0:
					c += 1
					flag = 1
				else:
					s += c
					c = 1
			else:
				if flag == 1:
					s = s + c
				flag = 0
				c = 0
		if flag == 1:
			return s + c
		else:
			return s


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		summa = 0
		count = 0
		flag = False
		for item in arr:
			if item == k:
				flag = True
				count += 1
			elif item < k:
				count += 1
			else:
				summa += count * flag
				flag = False
				count = 0
		return summa + count * flag


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		l = 0
		ans = 0
		maxi = -100000000000000.0
		for i in range(n):
			if arr[i] <= k:
				maxi = max(maxi, arr[i])
				l += 1
			else:
				if maxi == k:
					ans += l
					maxi = -100000000000000.0
				l = 0
		if maxi == k:
			ans += l
		return ans


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		ans = 0
		count = 0
		flag = False
		for i in range(n):
			if arr[i] < k:
				count += 1
			elif arr[i] == k:
				count += 1
				flag = True
			else:
				if flag:
					ans = ans + count
				flag = False
				count = 0
		if flag:
			ans = ans + count
		return ans


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		li1 = []
		li2 = []
		for i in range(0, n):
			if arr[i] <= k:
				li1.append(arr[i])
				if i == n - 1 and len(li1) != 0 and (li1[len(li1) - 1] <= k) and (k in li1):
					li2.append(len(li1))
			elif len(li1) != 0 and li1[len(li1) - 1] <= k and (k in li1):
				li2.append(len(li1))
				li1.clear()
			elif len(li1) != 0:
				li1.clear()
		return sum(li2)


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		(sum1, count, count1, count2) = (0, 0, 0, 0)
		for i in range(n):
			if arr[i] <= k:
				sum1 += arr[i]
				count += 1
				if arr[i] == k:
					count1 = 1
			else:
				if count1 == 1:
					count2 += count
				sum1 = 0
				count = 0
				count1 = 0
		if count1 == 1:
			count2 += count
		return count2


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		total = 0
		s = 0
		while s < n:
			l = s
			while l < n and arr[l] < k:
				l += 1
			if l == n:
				break
			elif arr[l] > k:
				s = l + 1
			elif arr[l] == k:
				r = l
				while r < n and arr[r] <= k:
					r += 1
				total += r - s
				s = r + 1
		return total


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		flag = False
		ans = 0
		val = 0
		for i in range(0, n):
			if arr[i] <= k:
				val += 1
				if not flag and arr[i] == k:
					flag = True
			else:
				if flag:
					ans += val
				val = 0
				flag = False
		if flag:
			ans += val
		return ans


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		count = 0
		subcount = 0
		ismax = False
		for i in arr:
			if i <= k:
				subcount += 1
				if i == k:
					ismax = True
			if i > k:
				if ismax:
					count += subcount
				ismax = False
				subcount = 0
		if ismax:
			count += subcount
		return count


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		flag = 0
		leng = 0
		summ_leng = 0
		for i in range(n):
			if arr[i] < k:
				leng += 1
			elif arr[i] == k:
				leng += 1
				flag = 1
			else:
				if flag == 1:
					summ_leng += leng
					flag = 0
				leng = 0
		if flag == 1:
			summ_leng += leng
		return summ_leng


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		max_len = 0
		length = 0
		flg = False
		for i in range(n):
			if arr[i] < k:
				length += 1
			elif arr[i] == k:
				length += 1
				flg = True
			else:
				if flg == True:
					max_len += length
				length = 0
				flg = False
		if flg == True:
			max_len += length
		return max_len


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		found = False
		summ = 0
		temp = 0
		for num in arr:
			if num == k:
				found = True
			if num <= k:
				temp += 1
			else:
				found = False
				temp = 0
			if found:
				summ += temp
				temp = 0
		return summ


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		l = []
		s = 0
		for i in arr:
			if i > k:
				if k in l:
					s = s + len(l)
				l = []
			else:
				l.append(i)
		if k in l:
			s = s + len(l)
		return s


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		max_ele = 0
		sum_f = 0
		p = 0
		for i in arr:
			if i <= k:
				p = p + 1
				if max_ele < i:
					max_ele = i
			else:
				if max_ele == k:
					max_ele = 0
					sum_f = sum_f + p
				p = 0
		if max_ele == k:
			sum_f = sum_f + p
		return sum_f


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		ans = 0
		l = 0
		arr.append(k + 1)
		hasK = False
		for i in range(n + 1):
			if arr[i] == k:
				hasK = True
			if arr[i] > k:
				if hasK:
					ans += i - l
				l = i + 1
				hasK = False
		return ans


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		ans = 0
		f = 0
		end = 0
		for x in range(n):
			if arr[x] == k:
				end += 1
				f = 1
			elif arr[x] > k:
				if f:
					ans += end
					f = 0
				end = 0
			else:
				end += 1
		if f:
			ans += end
		return ans


class Solution:

	def calculateMaxSumLength(self, array, n, k):
		(sum1, ct, flag) = (0, 0, 0)
		for i in range(len(array)):
			if array[i] <= k:
				ct += 1
				if array[i] == k:
					flag = 1
			else:
				if flag == 1:
					sum1 += ct
				ct = 0
				flag = 0
		if flag == 1:
			sum1 += ct
		return sum1


class Solution:

	def calculateMaxSumLength(self, arr, n, k):
		pairs = []
		lo = float('inf')
		hi = float('inf')
		for i in range(n):
			if arr[i] > k:
				pairs.append((lo, hi))
				lo = float('inf')
			else:
				lo = min(lo, i)
				hi = i
		if hi == n - 1 and lo != float('inf'):
			pairs.append((lo, hi))
		sums = 0
		for (x, y) in pairs:
			if x != float('inf') and y != float('inf'):
				for i in range(x, y + 1):
					if arr[i] == k:
						sums += y - x + 1
						break
		return sums