Commits

littledot5566 committed ef3b09f

srm559 div2 lvl1 BlockTower completed.

Comments (0)

Files changed (1)

src/srm559/BlockTower.java

+package srm559;
+
+public class BlockTower {
+
+	public int getTallest(int[] blockHeights) {
+		// even accumulates from the left
+		int[] even = new int[blockHeights.length];
+		// odd accumulates from the right
+		int[] odd = new int[blockHeights.length];
+		int maxHeight = 0;
+
+		int sum = 0;
+		for (int i = blockHeights.length - 1; i >= 0; i--) {
+			if (blockHeights[i] % 2 == 1)
+				sum += blockHeights[i];
+
+			odd[i] = sum;
+		}
+
+		sum = 0;
+
+		for (int i = 0; i < blockHeights.length; i++) {
+			if (blockHeights[i] % 2 == 0)
+				sum += blockHeights[i];
+
+			even[i] = sum;
+
+			// find the switching point
+			if (even[i] + odd[i] > maxHeight)
+				maxHeight = even[i] + odd[i];
+		}
+
+		return maxHeight;
+	}
+
+}