Programming Interview Practice - Max Consecutive Sum - 11/10/13

Max Consecutive Sum

/*
  Programming Interview Practice - Max Consecutive Sum

	Albert Elwin
	Website: http://albertelw.in
	Email: [email protected]
 */

#include <cstdio>
#include <vector>

std::vector<int> const findLargestSumOfContiguousElements(std::vector<int> const & initialArray)
{
	int currentSum = 0;
	for(auto i : initialArray) {
		currentSum += i;
	}

	unsigned int minId = 0;
	unsigned int maxId = initialArray.size() - 1;

	std::printf("Initial sum: %d (%u, %u)\n", currentSum, minId, maxId);

	unsigned int startId = minId;
	unsigned int endId = maxId;

	bool doLeft = true;

	while(startId < endId)
	{
		startId = (doLeft) ? startId + 1 : startId;
		endId = (!doLeft) ? endId - 1 : endId;

		doLeft = !doLeft;

		int nextSum = 0;
		for(auto i = initialArray.begin() + startId; i < initialArray.begin() + endId; i++) {
			nextSum += (*i);
		}

		std::printf("Next sum: %d (%u, %u)\n", nextSum, startId, endId);

		if(nextSum > currentSum)
		{
			currentSum = nextSum;

			minId = startId;
			maxId = endId;
		}
	}

	std::printf("Largest sum: %d (%u, %u)\n", currentSum, minId, maxId);

	return std::vector<int>(initialArray.begin() + minId, initialArray.begin() + maxId);
}

int main()
{
	std::vector<int> const vec = findLargestSumOfContiguousElements({-1, 5, 6, -2, 20, -50, 4});

	std::printf("Largest contiguous sum: ");

	for(auto i : vec) {
		std::printf("%d ", i);
	}

	return 0;
}