maximumSubArray.py

class maximumSubArraySum:
	def __init__(self, arr):
		self.arr = arr
	
	def sort(self):
		for a in range(len(self.arr)-1):
			for b in range(a+1, len(self.arr)):
				if (self.arr[a] > self.arr[b]):
					self.arr[b], self.arr[a] = self.arr[a], self.arr[b]
		print(self.arr)

	"""
		[-2, 1, -3, 4, -1, 2, 1, -5, 4]
		Look at all possible triplets: i, j, k
		Compute sum for each, identify the max_sum using max()
	"""
	def cubicSolution(self):
		bestSum = 0
		for a in range(len(self.arr)):
			for b in range(a, len(self.arr)):
				curSum = 0
				for c in range(a, b+1):
					curSum += self.arr[c]
				bestSum = max(curSum, bestSum)
		print(self.arr)
		print("best sum: " + str(bestSum))
	
	"""
		[-2, 1, -3, 4, -1, 2, 1, -5, 4]
		Look at all possible tuples i, j
		Compute running sum for each pair i and j, identify the max_sum using max()
	"""
	def quadraticSolution(self):
		bestSum = 0
		for a in range(len(self.arr)):
			curSum = 0
			for b in range(a, len(self.arr)):
				curSum += self.arr[b]
				bestSum = max(curSum, bestSum)
		print(self.arr)
		print("best sum: " + str(bestSum))
	
	"""
	Kadanes Algorithm:
		[-2, 1, -3, 4, -1, 2, 1, -5, 4]
	"""
	def linearSolution(self):
		bestSum = 0 ; curSum = 0
		for a in range(len(self.arr)):
			curSum = max(self.arr[a], curSum+self.arr[a])
			bestSum = max(curSum, bestSum)
		print(self.arr)
		print("best sum: " + str(bestSum))

if __name__ == '__main__':
	obj = maximumSubArraySum([-1,2,4,-3,5,2,-5,2])
	# obj.linearSolution()
	obj.sort()