Given an array Arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum.
Example 1:
Input:
N = 5
Arr[] = {1,2,3,-2,5}
Output:
9
Explanation:
Max subarray sum is 9
of elements (1, 2, 3, -2, 5) which 
is a contiguous subarray.
Example 2:
Input:
N = 4
Arr[] = {-1,-2,-3,-4}
Output:
-1
Explanation:
Max subarray sum is -1 
of element (-1)
Your Task:
You don't need to read input or print anything. The task is to complete the function maxSubarraySum() which takes Arr[] and N as input parameters and returns the sum of subarray with maximum sum.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{6}
-10^{7} ≤ A[i] ≤ 10^{7}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

    ##Complete this function

    #Function to find the sum of contiguous subarray with maximum sum.

    def maxSubArraySum(self,arr,N):

        ##Your code here

Solutions:
class Solution:

	def maxSubArraySum(self, arr, N):
		(maxsum, s) = (-10 ** 7, 0)
		for i in arr:
			s += i
			if maxsum < s:
				maxsum = s
			if s < 0:
				s = 0
		return maxsum


class Solution:

	def maxSubArraySum(self, a, n):
		p1 = 0
		p2 = 0
		ans = -10 ** 9 - 7
		s = 0
		for i in a:
			s += i
			ans = max(ans, s)
			if s < 0:
				s = 0
		return ans


class Solution:

	def maxSubArraySum(self, arr, N):
		for i in range(1, N):
			if arr[i - 1] > 0:
				arr[i] += arr[i - 1]
		return max(arr)


class Solution:

	def maxSubArraySum(self, Arr, N):
		maxSum = Arr[0]
		currentSum = Arr[0]
		for i in range(1, len(Arr)):
			currentSum = max(Arr[i], currentSum + Arr[i])
			maxSum = max(maxSum, currentSum)
		return maxSum


class Solution:

	def maxSubArraySum(self, arr, N):
		max_sum = arr[0]
		current_sum = arr[0]
		for i in range(1, N):
			current_sum = max(arr[i], current_sum + arr[i])
			max_sum = max(max_sum, current_sum)
		return max_sum


class Solution:

	def maxSubArraySum(self, arr, N):
		mtl = 0
		mev = 0
		negOrNot = all([i < 0 for i in arr])
		if negOrNot == True:
			return max(arr)
		for i in range(0, N):
			mev += arr[i]
			if mev < 0:
				mev = 0
			elif mtl < mev:
				mtl = mev
		return mtl


import sys

class Solution:

	def maxSubArraySum(self, arr, N):
		mini = -sys.maxsize
		maxi = -sys.maxsize
		summ = 0
		cou = 0
		for i in range(0, N):
			summ += arr[i]
			if summ < 0:
				summ = 0
			if summ > mini:
				mini = summ
			if arr[i] < 0:
				cou += 1
			if arr[i] > maxi:
				maxi = arr[i]
		if cou == N:
			return maxi
		return mini


class Solution:

	def maxSubArraySum(self, arr, N):
		maxSoFar = maxEndingHere = arr[0]
		for i in range(1, len(arr)):
			maxEndingHere = max(arr[i], maxEndingHere + arr[i])
			maxSoFar = max(maxSoFar, maxEndingHere)
		return maxSoFar


class Solution:

	def maxSubArraySum(self, arr, N):
		curr_sum = 0
		maxi = -math.inf
		for n in arr:
			curr_sum = curr_sum + n
			if curr_sum > maxi:
				maxi = curr_sum
			if curr_sum < 0:
				curr_sum = 0
		return maxi


class Solution:

	def maxSubArraySum(self, arr, N):
		curr_sum = 0
		maxi = -100
		for n in arr:
			curr_sum = curr_sum + n
			if curr_sum > maxi:
				maxi = curr_sum
			if curr_sum < 0:
				curr_sum = 0
		return maxi


class Solution:

	def maxSubArraySum(self, arr, N):
		max1 = arr[0]
		max2 = 0
		for i in range(N):
			max2 += arr[i]
			if max2 > max1:
				max1 = max2
			if max2 < 0:
				max2 = 0
		return max1


class Solution:

	def maxSubArraySum(self, arr, N):
		max_so_far = arr[0]
		max_ending_here = 0
		for i in range(N):
			max_ending_here = max_ending_here + arr[i]
			if max_so_far < max_ending_here:
				max_so_far = max_ending_here
			if max_ending_here < 0:
				max_ending_here = 0
		return max_so_far


class Solution:

	def maxSubArraySum(self, arr, N):
		cur_sum = 0
		max_sum = arr[0]
		for i in range(N):
			cur_sum += arr[i]
			if max_sum < cur_sum:
				max_sum = cur_sum
			if cur_sum < 0:
				cur_sum = 0
		return max_sum


class Solution:

	def maxSubArraySum(self, arr, N):
		maxsum = -1000000000.0
		sums = 0
		for i in range(0, N):
			sums = sums + arr[i]
			if sums > maxsum:
				maxsum = sums
			if sums < 0:
				sums = 0
		return maxsum


import sys

class Solution:

	def maxSubArraySum(self, arr, N):
		max_sum = -sys.maxsize
		max_sum_cont = 0
		for i in range(N):
			max_sum_cont += arr[i]
			if max_sum_cont > max_sum:
				max_sum = max_sum_cont
			if max_sum_cont < 0:
				max_sum_cont = 0
		return max_sum


class Solution:

	def maxSubArraySum(self, arr, N):
		import math
		currmax = 0
		max = -math.inf
		for i in arr:
			currmax += i
			if currmax > max:
				max = currmax
			if currmax < 0:
				currmax = 0
		return max


class Solution:

	def maxSubArraySum(self, arr, N):
		import math
		currSum = 0
		maxSum = -math.inf
		for i in arr:
			currSum += i
			if currSum > maxSum:
				maxSum = currSum
			if currSum < 0:
				currSum = 0
		return maxSum


class Solution:

	def maxSubArraySum(self, arr, N):
		maxsum = arr[0]
		n = len(arr)
		currsum = 0
		for i in range(n):
			currsum = currsum + arr[i]
			if currsum > maxsum:
				maxsum = currsum
			if currsum < 0:
				currsum = 0
		return maxsum


class Solution:

	def maxSubArraySum(self, arr, n):
		maxsum = arr[0]
		cursum = 0
		for i in arr:
			if cursum < 0:
				cursum = 0
			cursum += i
			maxsum = max(cursum, maxsum)
		return maxsum


class Solution:

	def maxSubArraySum(self, arr, N):
		max_sum = -10001
		cal_sum = 0
		for i in range(N):
			cal_sum += arr[i]
			if cal_sum > max_sum:
				max_sum = cal_sum
			if cal_sum < 0:
				cal_sum = 0
		return max_sum


class Solution:

	def maxSubArraySum(self, a, size):
		max_so_far = -9999999 - 1
		max_ending_here = 0
		for i in range(0, size):
			max_ending_here = max_ending_here + a[i]
			if max_so_far < max_ending_here:
				max_so_far = max_ending_here
			if max_ending_here < 0:
				max_ending_here = 0
		return max_so_far


class Solution:

	def maxSubArraySum(self, arr, N):
		s = 0
		ans = -float('inf')
		for i in arr:
			s += i
			if s > ans:
				ans = s
			if s < 0:
				s = 0
		return ans


class Solution:

	def maxSubArraySum(self, arr, N):
		sum = 0
		maxi = arr[0]
		for i in range(0, N):
			sum += arr[i]
			if sum > maxi:
				maxi = sum
			if sum < 0:
				sum = 0
		return maxi


class Solution:

	def maxSubArraySum(self, arr, N):
		dp = [0 for _ in range(N)]
		dp[0] = arr[0]
		for index in range(1, N):
			if arr[index] < dp[index - 1] + arr[index]:
				dp[index] = dp[index - 1] + arr[index]
			else:
				dp[index] = arr[index]
		return max(dp)


class Solution:

	def maxSubArraySum(self, arr, N):
		max_so_far = arr[0]
		curr = arr[0]
		i = 1
		while i < N:
			if curr > max_so_far:
				max_so_far = curr
			if curr < 0:
				curr = 0
			curr = curr + arr[i]
			i += 1
		return max(max_so_far, curr)


class Solution:

	def maxSubArraySum(self, arr, N):
		max_up_to_here = 0
		maxi = -99999
		for i in range(0, N):
			maxi = max(maxi, max_up_to_here + arr[i])
			if arr[i] + max_up_to_here < 0:
				max_up_to_here = 0
			else:
				max_up_to_here += arr[i]
		return maxi


class Solution:

	def maxSubArraySum(self, arr, N):
		if max(arr) < 0:
			return max(arr)
		s = 0
		p = 0
		for i in arr:
			p += i
			if p < 0:
				p = 0
			s = max(s, p)
		return s


class Solution:

	def maxSubArraySum(self, arr, N):
		curr = 0
		ans = float('-inf')
		for n in arr:
			curr = max(curr + n, n)
			ans = max(ans, curr)
		return ans


class Solution:

	def maxSubArraySum(self, arr, N):
		maxsum = arr[0]
		curr_sum = 0
		for i in range(len(arr)):
			curr_sum = curr_sum + arr[i]
			if curr_sum > maxsum:
				maxsum = curr_sum
			if curr_sum < 0:
				curr_sum = 0
		return maxsum


class Solution:

	def maxSubArraySum(self, arr, N):
		max = -1000000
		start = 0
		end = 0
		max_till_here = 0
		if N <= 0:
			return -1
		for r in range(0, N):
			max_till_here += arr[r]
			if max < max_till_here:
				max = max_till_here
				end = r
			if max_till_here < 0:
				max_till_here = 0
				start = r + 1
		return max


class Solution:

	def maxSubArraySum(self, arr, N):
		maxi = -float('inf')
		add = 0
		for i in range(N):
			add += arr[i]
			if add > maxi:
				maxi = add
			if add < 0:
				add = 0
		return maxi


class Solution:

	def maxSubArraySum(self, arr, N):
		maxi = -10000
		add = 0
		for i in range(N):
			add += arr[i]
			if add > maxi:
				maxi = add
			if add < 0:
				add = 0
		return maxi


class Solution:

	def maxSubArraySum(self, arr, N):
		import math
		sumele = 0
		max_sum = -math.inf
		for i in range(0, len(arr)):
			sumele = sumele + arr[i]
			max_sum = max(max_sum, sumele)
			if sumele < 0:
				sumele = 0
		return max_sum


class Solution:

	def maxSubArraySum(self, arr, N):
		max_sum = float('-inf')
		curr_sum = 0
		for x in arr:
			curr_sum += x
			max_sum = max(max_sum, curr_sum)
			if curr_sum < 0:
				curr_sum = 0
		return max_sum


class Solution:

	def maxSubArraySum(self, arr, N):
		curr = arr[0]
		final = arr[0]
		for i in range(1, len(arr)):
			curr = max(arr[i], curr + arr[i])
			final = max(curr, final)
		return final


class Solution:

	def maxSubArraySum(self, arr, N):
		max_sum = arr[0]
		curr_sum = arr[0]
		for i in arr[1:]:
			curr_sum = max(i + curr_sum, i)
			max_sum = max(max_sum, curr_sum)
		return max_sum


class Solution:

	def maxSubArraySum(self, nums, N):
		max_sum = current_sum = nums[0]
		for num in nums[1:]:
			current_sum = max(num, current_sum + num)
			max_sum = max(max_sum, current_sum)
		return max_sum


class Solution:

	def maxSubArraySum(self, arr, N):
		m = -10 ** 7
		import math
		s = 0
		m = -math.inf
		for i in range(N):
			s += arr[i]
			m = max(m, s)
			if s < 0:
				s = 0
		return m


from sys import maxsize

class Solution:

	def maxSubArraySum(self, a, size):
		max_so_far = -maxsize - 1
		max_ending_here = 0
		for i in range(0, size):
			max_ending_here = max_ending_here + a[i]
			if max_so_far < max_ending_here:
				max_so_far = max_ending_here
			if max_ending_here < 0:
				max_ending_here = 0
		return max_so_far


import sys

class Solution:

	def maxSubArraySum(self, arr, N):
		ans = arr[0]
		sum = 0
		for i in range(N):
			sum = sum + arr[i]
			ans = max(ans, sum)
			if sum < 0:
				sum = 0
		return ans


class Solution:

	def maxSubArraySum(self, Arr, N):
		if not Arr:
			return 0
		max_sum = Arr[0]
		current_sum = Arr[0]
		for i in range(1, N):
			current_sum = max(Arr[i], current_sum + Arr[i])
			max_sum = max(max_sum, current_sum)
		return max_sum


class Solution:

	def maxSubArraySum(self, arr, n):
		currsum = 0
		maxsum = -float('inf')
		for i in range(n):
			currsum = currsum + arr[i]
			if currsum > maxsum:
				maxsum = currsum
			if currsum < 0:
				currsum = 0
		return maxsum


class Solution:

	def maxSubArraySum(self, arr, N):
		summ = 0
		maxi = arr[0]
		for i in range(N):
			summ += arr[i]
			maxi = max(maxi, summ)
			if summ < 0:
				summ = 0
		return maxi


class Solution:

	def maxSubArraySum(self, arr, N):
		results = [arr[0]]
		for a in arr[1:]:
			if results[-1] < 0:
				results.append(a)
			else:
				if a < 0:
					results.append(results[-1])
				results[-1] += a
		return max(results)


class Solution:

	def maxSubArraySum(self, arr, N):
		local = -100
		glob = 0
		for i in range(0, N):
			glob = glob + arr[i]
			if local < glob:
				local = glob
			if glob < 0:
				glob = 0
		return local


class Solution:

	def maxSubArraySum(self, arr, N):
		local = -99999999999 - 1
		glob = 0
		for i in range(0, N):
			glob = glob + arr[i]
			if local < glob:
				local = glob
			if glob < 0:
				glob = 0
		return local


class Solution:

	def maxSubArraySum(self, arr, N):
		sum = 0
		k = 0
		for i in arr:
			sum += i
			if sum <= 0:
				sum = 0
			if sum > k:
				k = sum
		if k == 0:
			return max(arr)
		return k


class Solution:

	def maxSubArraySum(self, arr, N):
		start = 0
		end = 0
		sum = arr[0]
		s = []
		for i in range(N):
			while end < i:
				end += 1
				sum += arr[end]
				s.append(sum)
		return max(s)

class Solution:

	def maxSubArraySum(self, arr, N):
		max_score = -math.inf
		current_score = 0
		for i in arr:
			current_score += i
			max_score = max(max_score, current_score)
			if current_score < 0:
				current_score = 0
		return max_score


class Solution:

	def maxSubArraySum(self, arr, N):
		current_max = max_so_far = arr[0]
		for i in range(1, N):
			current_max = max(arr[i], current_max + arr[i])
			max_so_far = max(max_so_far, current_max)
		return max_so_far


class Solution:

	def maxSubArraySum(self, arr, N):
		ans = arr[0]
		sum = arr[0]
		for i in range(1, N):
			if sum >= 0:
				sum += arr[i]
			else:
				sum = arr[i]
			if ans < sum:
				ans = sum
		return ans


import sys

class Solution:

	def maxSubArraySum(self, arr, N):
		sum = 0
		MAX_SUM = -sys.maxsize
		for i in range(N):
			sum += arr[i]
			if sum > MAX_SUM:
				MAX_SUM = sum
			if sum < 0:
				sum = 0
		return MAX_SUM


class Solution:

	def maxSubArraySum(self, arr, N):
		sm = 0
		mx = float('-inf')
		for i in range(N):
			sm += arr[i]
			if sm > mx:
				mx = sm
			if sm < 0:
				sm = 0
		return mx


class Solution:

	def maxSubArraySum(self, arr, N):
		res = -999
		summ = 0
		for i in arr:
			summ += i
			res = max(summ, res)
			if summ < 0:
				summ = 0
		return res


class Solution:

	def maxSubArraySum(self, arr, N):
		max_sum_till_now = -10000000000
		curr_sum = 0
		for i in range(N):
			curr_sum += arr[i]
			max_sum_till_now = max(max_sum_till_now, curr_sum)
			if curr_sum < 0:
				curr_sum = 0
		return max_sum_till_now


class Solution:

	def maxSubArraySum(self, arr, N):
		ans = max(arr)
		mtt = arr[0]
		for i in range(1, N):
			mtt = max(mtt + arr[i], arr[i])
			ans = max(ans, mtt)
		return ans


class Solution:

	def maxSubArraySum(self, arr, N):
		max_so_far = arr[0]
		max_end_here = 0
		for i in arr:
			max_end_here += i
			if max_end_here > max_so_far:
				max_so_far = max_end_here
			if max_end_here < 0:
				max_end_here = 0
		return max_so_far


class Solution:

	def maxSubArraySum(self, arr, N):
		(maxi, curr) = (arr[0], 0)
		for x in arr:
			curr += x
			maxi = max(maxi, curr)
			if curr < 0:
				curr = 0
		return maxi


class Solution:

	def maxSubArraySum(self, arr, N):
		max_sum = float('-inf')
		current_sum = 0
		for i in range(N):
			current_sum += arr[i]
			if current_sum > max_sum:
				max_sum = current_sum
			if current_sum < 0:
				current_sum = 0
		return max_sum


class Solution:

	def maxSubArraySum(self, arr, N):
		max_score = -math.inf
		current_score = 0
		for i in arr:
			current_score += i
			max_score = max(max_score, current_score)
			if current_score < 0:
				current_score = 0
		return max_score


class Solution:

	def maxSubArraySum(self, arr, N):
		cur_max = float('-inf')
		ans = max(arr)
		for i in range(1, N):
			arr[i] += arr[i - 1]
		i = N - 1
		while i >= 0:
			if arr[i] >= cur_max:
				cur_max = arr[i]
				ans = max(ans, cur_max)
			else:
				ans = max(ans, cur_max - arr[i])
			i -= 1
		return ans


class Solution:

	def maxSubArraySum(self, arr, n):
		maxending = 0
		maxending = arr[0]
		res = arr[0]
		for i in range(1, n):
			maxending = max(arr[i], maxending + arr[i])
			res = max(maxending, res)
		return res


class Solution:

	def maxSubArraySum(self, arr, N):
		sumsofar = -9999999
		currentsum = 0
		for i in arr:
			currentsum += i
			if sumsofar < currentsum:
				sumsofar = currentsum
			if currentsum <= 0:
				currentsum = 0
		return sumsofar


class Solution:

	def maxSubArraySum(self, arr, n):
		maxendingsum = [0] * n
		maxendingsum[0] = arr[0]
		s = 0
		res = arr[0]
		for i in range(1, n):
			if i > 0:
				s = maxendingsum[i - 1] + arr[i]
				maxendingsum[i] = max(arr[i], s)
			else:
				maxendingsum[i] = arr[i]
			res = max(maxendingsum[i], res)
		return res


class Solution:

	def maxSubArraySum(self, arr, N):
		max_r = arr[0]
		max_s = arr[0]
		for i in range(1, len(arr)):
			max_r = max(arr[i], arr[i] + max_r)
			max_s = max(max_r, max_s)
		return max_s


class Solution:

	def maxSubArraySum(self, arr, N):
		nums = arr
		res_fi_sum = nums[0]
		res_sum = 0
		for i in nums:
			if i < 0:
				pass
			if res_sum < 0:
				res_sum = 0
			res_sum += i
			res_fi_sum = max(res_sum, res_fi_sum)
		return res_fi_sum


class Solution:

	def maxSubArraySum(self, arr, N):
		max = -99999999999
		sum_subarr = 0
		for i in range(N):
			sum_subarr = sum_subarr + arr[i]
			if sum_subarr > max:
				max = sum_subarr
			if sum_subarr < 0:
				sum_subarr = 0
		return max


class Solution:

	def maxSubArraySum(self, arr, N):
		max_sum = arr[0]
		cursum = 0
		i = 0
		while i < N:
			if cursum < 0:
				cursum = 0
			cursum += arr[i]
			max_sum = max(max_sum, cursum)
			i += 1
		return max_sum


class Solution:

	def maxSubArraySum(self, arr, N):
		sumed = arr[0]
		maxsum = arr[0]
		for i in range(1, N):
			sumed = max(arr[i], arr[i] + sumed)
			maxsum = max(maxsum, sumed)
		return maxsum


class Solution:

	def maxSubArraySum(self, A, N):
		max_sum = A[0]
		sum = 0
		for i in A:
			sum += i
			if sum > max_sum:
				max_sum = sum
			if sum < 0:
				sum = 0
		return max_sum


class Solution:

	def maxSubArraySum(self, arr, n):
		maxSum = arr[0]
		currentSum = arr[0]
		for i in range(1, n):
			currentSum = max(arr[i], currentSum + arr[i])
			if maxSum < currentSum:
				maxSum = currentSum
		return maxSum