alternateSum_O(n)

	private static int altKadanes(int[] array, int sign) {
		int maxCurrent = 0;
		int maxGlobal = maxCurrent;
		for(int i = 0; i < array.length; i++) {
			int signedVal = (array[i])*((int)(Math.pow(-1,(i + sign))));
			maxCurrent = Math.max(signedVal, maxCurrent + signedVal);
			if(maxCurrent > maxGlobal) {
				maxGlobal = maxCurrent;
			}
		}
		return maxGlobal;
	}

	public static int alternateSum(int[] array)
	{
		int firstMax = altKadanes(array,0);
		int secondMax = altKadanes(array, 1);

		return Math.max(firstMax, secondMax);

	}