Codechef June 2013 Delish

I worked for hours on this one, just for my solution to be rejected. =( But the hard work paid off, my solution came very close to the one in the editorial =) This one didn't get accepted:

	# just some test inut
	# 10 -1 -1 -1 -1 1 -9 8 -99 2000 0 -1 -1
	# and just playing around with DP
	# 6 -4 -3 -2 -1
	# 7 -3 -2 -1 0 1
	# -2 -12 -11 -10 -9 -8 -9
	# 6 -4 -3 -2 -1 0 -1 8
	# -84 -94 -103 -102 -101 -100 -99 -100 -91
	# Managed to hit upon this property after thinking for hours
	# Edit: This is mentioned in the editorial too
	# Property 1:
	# j and k cannot have gap
	# because if have gap > 0, one side will eat it up
	# hence for each middle position j or k
	# calculate the min/max values for each section, one to the left
	# and one to the right of j/k
	# then calculate the largest absolute difference between each
	# pair of left/right sections
	# Property 2:
	# if I need the minimum value, and the sum of all elements
	# before this is > 0, then why shouldn't I leave them all out?
	# I should do this checking at every point where the previous
	# value is positive and my current number is negative.
	# EDIT: from the editorial I learnt that I should check at every
	# point, not just the points I've chosen.
	# need to speed it up
	import sys
	T = int(sys.stdin.readline().strip())
	for z in range(T):
	N = int(sys.stdin.readline().strip())
	numbers = []
	leftMins = []
	leftMaxs = []
	rightMins = []
	rightMaxs = []
	max_delish = 0
	lines = sys.stdin.readline().strip()
	for n in lines.split(" "):
	numbers.append(int(n))
	leftMins.append(10000001)
	leftMaxs.append(-10000001)
	rightMins.append(10000001)
	rightMaxs.append(-10000001)
	i_min = 0
	i_max = 0
	leftMins[0] = numbers[0]
	leftMaxs[0] = numbers[0]
	rightMins[len(numbers)-1] = numbers[len(numbers)-1]
	rightMaxs[len(numbers)-1] = numbers[len(numbers)-1]
	# for left sides
	for j in range(1,N-1):
	# for minimums
	if numbers[j] <= 0 and numbers[j-1] > 0:
	# try to move i
	if leftMins[j-1] >= 0:
	i_min = j
	leftMins[j] = numbers[j]
	else:
	leftMins[j] = leftMins[j-1] + numbers[j]
	else:
	leftMins[j] = leftMins[j-1] + numbers[j]
	# for maximums
	if numbers[j] >= 0 and numbers[j-1] < 0:
	# try to move i
	if leftMaxs[j-1] <= 0:
	i = j
	leftMaxs[j] = numbers[j]
	else:
	leftMaxs[j] = leftMaxs[j-1] + numbers[j]
	else:
	leftMaxs[j] = leftMaxs[j-1] + numbers[j]
	l_min = len(numbers)-1
	l_max = len(numbers)-1
	# for right sides
	for z in range(1,N-1):
	j = N - 1 - z
	# for minimums
	if numbers[j] <= 0 and numbers[j+1] > 0:
	# try to move i
	if rightMins[j+1] >= 0:
	l_min = j
	rightMins[j] = numbers[j]
	else:
	rightMins[j] = rightMins[j+1] + numbers[j]
	else:
	rightMins[j] = rightMins[j+1] + numbers[j]
	# for maximums
	if numbers[j] >= 0 and numbers[j+1] < 0:
	# try to move i
	if rightMaxs[j+1] <= 0:
	l_max = j
	rightMaxs[j] = numbers[j]
	else:
	rightMaxs[j] = rightMaxs[j+1] + numbers[j]
	else:
	rightMaxs[j] = rightMaxs[j+1] + numbers[j]
	max_delish = 0
	for j in range(N-1):
	k = j+1
	delish = max(rightMaxs[k] - leftMins[j], leftMaxs[j] - rightMins[k])
	if delish > max_delish:
	max_delish = delish
	print max_delish

view raw gistfile1.txt hosted with ❤ by GitHub

Did my correction and got it accepted:

	# Correction after viewing the editorial
	# Property 1:
	#j and k cannot have gap
	#because if have gap > 0, one side will eat it up
	# hence for each middle position j or k
	# calculate the min/max values for each section, one to the left
	# and one to the right of j/k
	# then calculate the largest absolute difference between each
	# pair of left/right sections
	import sys
	T = int(sys.stdin.readline().strip())
	for z in range(T):
	N = int(sys.stdin.readline().strip())
	numbers = []
	leftMins = []
	leftMaxs = []
	rightMins = []
	rightMaxs = []
	max_delish = 0
	lines = sys.stdin.readline().strip()
	for n in lines.split(" "):
	numbers.append(int(n))
	leftMins.append(10000001)
	leftMaxs.append(-10000001)
	rightMins.append(10000001)
	rightMaxs.append(-10000001)
	leftMins[0] = numbers[0]
	leftMaxs[0] = numbers[0]
	rightMins[len(numbers)-1] = numbers[len(numbers)-1]
	rightMaxs[len(numbers)-1] = numbers[len(numbers)-1]
	# for left sides
	for j in range(1,N-1):
	# for minimums
	if leftMins[j-1] >= 0:
	leftMins[j] = numbers[j]
	else:
	leftMins[j] = leftMins[j-1] + numbers[j]
	# for maximums
	if leftMaxs[j-1] <= 0:
	leftMaxs[j] = numbers[j]
	else:
	leftMaxs[j] = leftMaxs[j-1] + numbers[j]
	# for right sides
	for z in range(1,N-1):
	j = N - 1 - z
	# for minimums
	if rightMins[j+1] >= 0:
	rightMins[j] = numbers[j]
	else:
	rightMins[j] = rightMins[j+1] + numbers[j]
	# for maximums
	if rightMaxs[j+1] <= 0:
	rightMaxs[j] = numbers[j]
	else:
	rightMaxs[j] = rightMaxs[j+1] + numbers[j]
	max_delish = 0
	for j in range(N-1):
	k = j+1
	delish = max(rightMaxs[k] - leftMins[j], leftMaxs[j] - rightMins[k])
	if delish > max_delish:
	max_delish = delish
	print max_delish

view raw gistfile1.txt hosted with ❤ by GitHub