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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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; 

  }

}

TestNG test cases for this problem which all passed:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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);

  } 

}