Given an array, get the sub sequence that of larget sum.

largestsum.lua

--
-- Given an array, get the sub sequence that of larget sum.
--
function printArray(array)
	for i=1, #array do
		io.write(array[i]) -- parameter is a variable, () can't be ignored.
		io.write(" ")
	end
end

-- O(n^2) - brutal force: calculate all sum(i, j) and get the max
function largestSum1(array) 
	local maxSum = array[1]
	local first = 1
	local last = 1
	
	for i = 1, #array do
		local curSum = 0
		for j = i, #array do
			curSum = curSum + array[j]
			if (curSum > maxSum) then
				maxSum = curSum
				first = i
				last = j
			end
		end
	end
	
	for i=first, last do
		io.write(array[i]);
		io.write " "
	end
end

-- O(n) - as you walk through the array (accumulate & check max), if the sum of previous n elments < 0, you should restart from next element.
function largestSum2(array)
	local maxSum = array[1]
	local first = 1
	local last = 1
	
	local curSum = 0
	local start = 1
	for i = 1, #array do
		curSum = curSum + array[i]
		if(curSum > maxSum) then 
			maxSum = curSum
			first = start
			last = i
		end
		
		if(curSum < 0) then
			start = i + 1;
		end
	end
	
	for i=first, last do
		io.write(array[i]);
		io.write " "
	end
end

function test(array) 
	printArray(array)
	print()
	largestSum1(array)
	print()
	largestSum2(array)
	print()
	print()
end


-- testing
test {1}
test {1, 2}
test {1, 2, -3}
test {1, 2, -3, 3}
test {1, 2, -3, 4}
test {1, 2, 5, 4 ,2, 6}
test {-1, 2, 5, 4 ,2, 6}
test {-1, -2, 5, 4 ,2, 6}
test {1, 2, 5, -4 ,2, 6}

result:
$ lua largestsum.lua
1
1
1

1 2
1 2
1 2

1 2 -3
1 2
1 2

1 2 -3 3
1 2
1 2

1 2 -3 4
1 2 -3 4
1 2 -3 4

1 2 5 4 2 6
1 2 5 4 2 6
1 2 5 4 2 6

-1 2 5 4 2 6
2 5 4 2 6
2 5 4 2 6

-1 -2 5 4 2 6
5 4 2 6
5 4 2 6

1 2 5 -4 2 6
1 2 5 -4 2 6
1 2 5 -4 2 6