Given an array of N integers and Q queries, each query having a range from index L to R. Find the maximum prefix-sum for the range L to R.
Note: Assume 0 based indexing.
Example 1:
Input: 
a[ ] = {-1, 2, 3, -5} 
Q = 2
L_{1} = 0, R_{1} = 3
L_{2} = 1, R_{2} = 3
Output:
4 5
Explanation:
The range (0, 3) in the 1st query is {-1, 2, 3, -5}, hence, 
the max prefix-sum will be -1 + 2 + 3 = 4. The range (1, 3) 
in the 2nd query is {2, 3, -5}, hence, the max prefix-sum 
will be 2 + 3 = 5.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function maxPrefixes() which takes the array A[], its size N, array L[] and R[] and their size Q as input parameters and returns a vector storing the required answer for every query.
Expected Time Complexity: O(N*Q)
Expected Auxiliary Space: O(1)
Constraints: 
1 ≤ N ≤ 10^{4}
-10^{4} ≤ A[i]≤ 10^{4}
1 ≤ Q ≤ 10^{4}
0 ≤ L[i] ≤ R[i] < N

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Range queries

Segment trees revisited

Starter code: #User function Template for python3



class Solution:

    def maxPrefixes(self, a, L, R, N, Q):

        # code here

Solutions:
class Solution:

	def maxPrefixes(self, a, L, R, N, Q):
		for i in range(N - 1):
			a[i + 1] += a[i]
		a.insert(0, 0)
		output = []
		for i in range(Q):
			output.append(max(a[L[i] + 1:R[i] + 2]) - a[L[i]])
		return output


class Solution:

	def maxPrefixes(self, a, L, R, N, Q):
		res = []
		for i in range(Q):
			l = L[i]
			r = R[i]
			maxi = -99999
			summ = 0
			for j in range(l, r + 1, 1):
				summ += a[j]
				if summ > maxi:
					maxi = summ
			res.append(maxi)
		return res


class Solution:

	def maxPrefixes(self, a, L, R, N, Q):
		ans = []
		for i in range(Q):
			d = []
			c = 0
			for j in range(L[i], R[i] + 1):
				c += a[j]
				d += [c]
			ans += [max(d)]
		return ans


class Solution:

	def maxPrefixes(self, a, L, R, N, Q):
		pre = []
		for i in range(N):
			if not pre:
				pre.append(a[i])
			else:
				pre.append(a[i] + pre[-1])
		res = []
		for i in range(Q):
			(p, q) = (L[i], R[i])
			diff = 0
			if p >= 1:
				diff = pre[p - 1]
			curr = pre[p] - diff
			for j in range(p + 1, q + 1):
				curr = max(curr, pre[j] - diff)
			res.append(curr)
		return res


class Solution:

	def maxPrefixes(self, a, l, r, n, q):
		res = []
		s = []
		s.append(a[0])
		for i in range(1, n):
			s.append(a[i] + s[i - 1])
		for i in range(q):
			p = s[l[i] - 1] if l[i] > 0 else 0
			u = s[l[i]] - p
			for j in range(l[i] + 1, r[i] + 1):
				u = max(u, s[j] - p)
			res.append(u)
		return res


class Solution:

	def maxPrefixes(self, a, L, R, N, Q):
		ans = []
		for i in range(Q):
			l = L[i]
			r = R[i]
			summ = 0
			maxSum = float('-inf')
			for j in range(l, r + 1):
				summ += a[j]
				maxSum = max(summ, maxSum)
			ans.append(maxSum)
		return ans


class Solution:

	def maxPrefixes(self, a, L, R, N, Q):
		result = []
		for i in range(Q):
			temp = -10 ** 4 - 1
			m = a[L[i]]
			for j in range(L[i] + 1, R[i] + 1):
				temp = max(temp, m)
				m = m + a[j]
			temp = max(temp, m)
			result.append(temp)
		return result


class Solution:

	def get_maxsum(self, arr):
		max_sum = -12345678
		l = len(arr)
		curr_sum = 0
		for i in range(l):
			curr_sum += arr[i]
			max_sum = max(max_sum, curr_sum)
		return max_sum

	def maxPrefixes(self, a, L, R, N, Q):
		res = []
		for i in range(Q):
			l1 = L[i]
			r1 = R[i]
			temp = self.get_maxsum(a[l1:r1 + 1])
			res.append(temp)
		return res


class Solution:

	def maxPrefixes(self, a, L, R, N, Q):
		ans = []
		for i in range(Q):
			(s, b) = (a[L[i]], a[L[i]])
			for j in range(L[i] + 1, R[i] + 1):
				b += a[j]
				s = max(s, b)
			ans.append(s)
		return ans


from math import inf

class Solution:

	def maxPrefixes(self, x, L, R, N, Q):
		p = [0]
		for i in range(N):
			p.append(x[i] + p[-1])

		def f(i, j):
			if i > j:
				return
			pp = 0
			ma = -inf
			for q in range(i, j + 1):
				pp += x[q]
				ma = max(ma, pp)
			dp[i, j] = ma
			if i == j:
				return
			f(i, (i + j) // 2)
			f((i + j) // 2 + 1, j)
		dp = {}

		def query(i, j, ii, jj):
			if j < ii or jj < i:
				return -inf
			if ii <= i and j <= jj:
				return p[i] - p[ii] + dp[i, j]
			m = (i + j) // 2
			return max(query(i, m, ii, jj), query(m + 1, j, ii, jj))
		z = []
		f(0, N - 1)
		for i in range(len(R)):
			z.append(query(0, N - 1, L[i], R[i]))
		return z


from math import inf

class Solution:

	def maxPrefixes(self, x, L, R, N, Q):
		res = []
		for i in range(len(R)):
			(l, r) = (L[i], R[i])
			p = 0
			ma = -inf
			for i in range(l, r + 1):
				p += x[i]
				ma = max(p, ma)
			res.append(ma)
		return res


class Solution:

	def maxPrefixes(self, a, L, R, N, Q):
		res = []
		for i in range(Q):
			l = L[i]
			r = R[i]
			maxx = -99999
			cur = 0
			for j in range(l, r + 1):
				cur += a[j]
				if cur > maxx:
					maxx = cur
			res.append(maxx)
		return res
if __name__ == '__main__':
	T = int(input())
	while T > 0:
		(n, q) = map(int, input().split())
		l = [0] * q
		r = [0] * q
		a = list(map(int, input().split()))
		st = list(map(int, input().split()))
		for i in range(0, 2 * q, 2):
			l[i // 2] = st[i]
			r[i // 2] = st[i + 1]
		ob = Solution()
		res = ob.maxPrefixes(a, l, r, n, q)
		for i in res:
			print(i, end=' ')
		print()
		T -= 1


class Solution:

	def maxPrefixes(self, a, L, R, N, Q):
		ans = []
		for i in range(Q):
			res = -float('inf')
			cur = 0
			for j in range(L[i], R[i] + 1):
				cur += a[j]
				res = max(cur, res)
			ans.append(res)
		return ans


class Solution:

	def maxPrefixes(self, a, L, R, N, Q):
		i = 0
		ans = []
		while i < Q:
			maxval = -float('inf')
			pre = 0
			j = L[i]
			while j <= R[i]:
				pre += a[j]
				maxval = max(maxval, pre)
				j += 1
			ans.append(maxval)
			i += 1
		return ans


class Solution:

	def maxPrefixes(self, a, L, R, N, Q):

		def build(l, r):
			ans = 0
			res = -10000000000
			for i in range(l, r + 1):
				ans += a[i]
				res = max(res, ans)
			return res
		ans = []
		for i in range(Q):
			x = build(L[i], R[i])
			ans.append(x)
		return ans


class Solution:

	def maxPrefixes(self, arr, L, R, N, Q):
		output = []
		for j in range(Q):
			sum1 = 0
			maxPreSumInRange = arr[L[j]]
			left = L[j]
			right = R[j]
			for i in range(left, N):
				sum1 += arr[i]
				if i >= left:
					maxPreSumInRange = max(sum1, maxPreSumInRange)
				if i == right:
					output.append(maxPreSumInRange)
					break
		return output


import math

class Solution:

	def maxPrefixes(self, arr, L, R, N, Q):
		ret = []
		for i in range(Q):
			ms = -math.inf
			s = 0
			for j in range(L[i], R[i] + 1):
				s += arr[j]
				ms = max(ms, s)
			ret.append(ms)
		return ret


class Solution:

	def maxPrefixes(self, a, L, R, N, Q):
		result = []
		for i in range(0, len(L)):
			start = L[i]
			end = R[i]
			max_sum = a[start]
			sum1 = a[start]
			start += 1
			while start <= end:
				sum1 += a[start]
				if sum1 > max_sum:
					max_sum = sum1
				start += 1
			result.append(max_sum)
		return result


class Solution:

	def maxPrefixes(self, a, L, R, N, Q):
		ans = []
		for i in range(Q):
			l = L[i]
			r = R[i]
			res = 0
			maxm = a[l]
			for i in range(l, r + 1):
				res = res + a[i]
				if res > maxm:
					maxm = res
			ans.append(maxm)
		return ans


def query(tree, start, end, ss, se, si):
	ans = [0, 0]
	if se < start or ss > end:
		return ans
	if ss <= start and se >= end:
		return tree[si]
	mid = (start + end) // 2
	if ss > mid:
		return query(tree, mid + 1, end, ss, se, si * 2 + 2)
	if se <= mid:
		return query(tree, start, mid, ss, se, si * 2 + 1)
	left = query(tree, start, mid, ss, se, si * 2 + 1)
	right = query(tree, mid + 1, end, ss, se, si * 2 + 2)
	ans[0] = left[0] + right[0]
	ans[1] = max(left[1], left[0] + right[1])
	return ans

def build(tree, a, start, end, si):
	if start == end:
		tree[si][0] = a[start]
		tree[si][1] = a[start]
		return
	mid = (start + end) // 2
	build(tree, a, start, mid, si * 2 + 1)
	build(tree, a, mid + 1, end, si * 2 + 2)
	tree[si][0] = tree[si * 2 + 1][0] + tree[si * 2 + 2][0]
	tree[si][1] = max(tree[si * 2 + 1][1], tree[si * 2 + 1][0] + tree[si * 2 + 2][1])

class Solution:

	def maxPrefixes(self, a, L, R, N, Q):
		tree = [[0, 0] for i in range(4 * N)]
		build(tree, a, 0, N - 1, 0)
		ans = []
		for i in range(Q):
			x = query(tree, 0, N - 1, L[i], R[i], 0)
			ans.append(x[1])
		return ans


class Solution:

	def maxPrefixes(self, a, L, R, N, Q):
		lis = []
		for i in range(Q):
			maxi = -10 ** 9
			temp = 0
			for j in range(L[i], R[i] + 1):
				maxi = max(a[j] + temp, maxi)
				temp += a[j]
			lis.append(maxi)
		return lis