#include"SingleCoreSolution.h"
namespace SingleCoreSolution {
	std::string Solution::TrickOrTreat(const std::vector<int>& pieces,
		const int homes, const int max) {

		//calculate prefix sum;
		std::vector<int> prefixSum(homes + 1, 0);
		for (int i = 0; i < homes; ++i) {
			prefixSum[i + 1] = prefixSum[i] + pieces[i];
		}

		//use two pointers
		int left = -1, right = 0;
		int maxLeftId = 0, maxRightId = 0;
		int maxCandy = -1;

		while (right <= homes) {
			//shrink left
			do { left++; } while (left < right && prefixSum[right] - prefixSum[left] > max);

			//expand right
			do { right++; } while (right <= homes && prefixSum[right] - prefixSum[left] <= max);

			//calculate and update status
			int currCandy = prefixSum[right - 1] - prefixSum[left];
			if ((right - 1) != left && currCandy > maxCandy) {
				maxLeftId = left;
				maxRightId = right;
				maxCandy = currCandy;
			}
		}
		if (maxCandy == -1) {
			return "Don't go here\n";
		}
		else {
			return "Start at home " + std::to_string(maxLeftId + 1) +
				" and go to home " + std::to_string(maxRightId - 1) +
				" getting " + std::to_string(maxCandy) +
				" pieces of candy\n";
		}
	}

}//SingleCoreSolution