MaxProfit – Codility – Solution

Java solution to Codility MaxProfit problem (Lesson 9 – Maximum Slice) which scored 100%. The problem is to find the maximum possible profit from a stock price ticker.

The strategy is to convert profit table to delta table so can use max slice sum technique.

[cc lang="java" escaped="true"]
package com.codility.lesson09.maxslice;

public class MaxProfit {

	public int solution(int[] A) {
		if(A.length < 2) return 0; //for empty array or 1 element array, no profit can be realized
		
		//convert profit table to delta table so can use max slice technique
		int [] deltaA = new int[A.length];
		deltaA[0] = 0;
		for(int i=1; i<A.length; i++) {
			deltaA[i] = A[i] - A[i-1];
		}
		
		int absoluteMax = deltaA[0];
		int localMax = deltaA[0];
		int nextSum = 0;
		int currentElement = 0;
		
		for (int i = 1; i < deltaA.length; i++) { currentElement = deltaA[i]; nextSum = localMax + currentElement; localMax = Math.max(deltaA[i], nextSum); absoluteMax = Math.max(absoluteMax, localMax); } if(absoluteMax > 0) return absoluteMax;
		
		return 0; 
	}
}
[/cc]

TestNG test cases for this problem which all passed:

[cc lang="java" escaped="true"]
package test.com.codility.lesson09.maxslice;

import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

import com.codility.lesson09.maxslice.MaxProfit;

public class MaxProfitTests {
	private MaxProfit solution;
	
	@BeforeTest
	public void setUp() {
		solution = new MaxProfit();
	}

	@DataProvider(name = "test1")
	public Object [][] createData1() {
		return new Object [][] {
			new Object [] { new int [] { 23171, 21011, 21123, 21366, 21013, 21367 }, 356 },
			new Object [] { new int [] { 23171 }, 0 },
			new Object [] { new int [] { }, 0 },
		};
	}

	@Test(dataProvider = "test1")
	public void verifySolution(int [] pA, int pExpected) {		
		Assert.assertEquals(solution.solution(pA), pExpected);
	}	
}
[/cc]