Codility Lesson 09

9.1 - Max Profit

An array A consisting of N integers is given. It contains daily prices of a stock share for a period of N consecutive days. If a single share was bought on day P and sold on day Q, where 0 ≤ P ≤ Q < N, then the profit of such transaction is equal to A[Q] − A[P], provided that A[Q] ≥ A[P]. Otherwise, the transaction brings loss of A[P] − A[Q].

For example, consider the following array A consisting of six elements such that:

  A[0] = 23171
  A[1] = 21011
  A[2] = 21123
  A[3] = 21366
  A[4] = 21013
  A[5] = 21367

If a share was bought on day 0 and sold on day 2, a loss of 2048 would occur because A[2] − A[0] = 21123 − 23171 = −2048. If a share was bought on day 4 and sold on day 5, a profit of 354 would occur because A[5] − A[4] = 21367 − 21013 = 354. Maximum possible profit was 356. It would occur if a share was bought on day 1 and sold on day 5.

Write a function,

class Solution 
{
  public int solution(int[] A); 
}

that, given an array A consisting of N integers containing daily prices of a stock share for a period of N consecutive days, returns the maximum possible profit from one transaction during this period. The function should return 0 if it was impossible to gain any profit.

For example, given array A consisting of six elements such that:

  A[0] = 23171
  A[1] = 21011
  A[2] = 21123
  A[3] = 21366
  A[4] = 21013
  A[5] = 21367

the function should return 356, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..400,000];
• each element of array A is an integer within the range [0..200,000].

using System;
using System.Linq;
using System.Collections.Generic;

/**
 * 9.1 - Max Profit
 * Paulo Santos
 * 14.Dec.2022
 */
class Solution {
    public int solution(int[] A) {

        /*
         * Check the input
         */
        if (A == null)
            throw new ArgumentNullException();
        if (A.Length == 0)
            return 0;

        var min = A[0];
        var difs = new List<int>();
        var dif = 0;

        for (var i = 1; i < A.Length; i++) {
            dif = Math.Max((A[i] - min), dif);
            if (min > A[i]) {
                difs.Add(dif);
                dif = 0;
                min = A[i];
            }
        }
        difs.Add(dif);

        return difs.Max();
    }
}

---

9.2 - Max Slice Sum

A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

Write a function:

class Solution 
{
  public int solution(int[] A); 
}

that, given an array A consisting of N integers, returns the maximum sum of any slice of A.

For example, given array A such that:

A[0] = 3  A[1] = 2  A[2] = -6
A[3] = 4  A[4] = 0

the function should return 5 because:

• (3, 4) is a slice of A that has sum 4,
• (2, 2) is a slice of A that has sum −6,
• (0, 1) is a slice of A that has sum 5,
• no other slice of A has sum greater than (0, 1).

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..1,000,000];
• each element of array A is an integer within the range [−1,000,000..1,000,000];
• the result will be an integer within the range [−2,147,483,648..2,147,483,647].

using System;

/**
 * 9.2 - Max Slice Sum
 * Paulo Santos
 * 15.Dec.2022
 */
class Solution {
    public int solution(int[] A) {

        /*
         * Check the input
         */
        if (A == null) 
            throw new ArgumentNullException();

        int aMax = A[0];
        int lMax = A[0];
        int sum = 0;
       
        for (int i = 1; i < A.Length; i++) {
          sum = lMax + A[i];
          lMax = Math.Max(A[i], sum);
          aMax = Math.Max(aMax, lMax);
        }
        return aMax;
    }
}

---

9.3 - Max Double Slice Sum

A non-empty array A consisting of N integers is given.

A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a double slice.

The sum of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1].

For example, array A such that:

    A[0] = 3
    A[1] = 2
    A[2] = 6
    A[3] = -1
    A[4] = 4
    A[5] = 5
    A[6] = -1
    A[7] = 2

contains the following example double slices:

• double slice (0, 3, 6), sum is 2 + 6 + 4 + 5 = 17,
• double slice (0, 3, 7), sum is 2 + 6 + 4 + 5 − 1 = 16,
• double slice (3, 4, 5), sum is 0.

The goal is to find the maximal sum of any double slice.

Write a function:

class Solution 
{
  public int solution(int[] A); 
}

that, given a non-empty array A consisting of N integers, returns the maximal sum of any double slice.

For example, given:

    A[0] = 3
    A[1] = 2
    A[2] = 6
    A[3] = -1
    A[4] = 4
    A[5] = 5
    A[6] = -1
    A[7] = 2

the function should return 17, because no double slice of array A has a sum of greater than 17.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [3..100,000];
• each element of array A is an integer within the range [−10,000..10,000].

using System;

/**
 * 9.3 - Max Double Slice
 * Paulo Santos
 * 15.Dec.2022
 */
class Solution {
    public int solution(int[] A) {
        var len = A.Length;
        var s1Max = new int[len];
        var s2Max = new int[len];

        for(var i = 1; i < A.Length - 1; i++) { 
            s1Max[i] = Math.Max(s1Max[i - 1] + A[i], 0); 
        }

        for(int i = A.Length - 2; i > 0; i--) {
            s2Max[i] = Math.Max(s2Max[i + 1] + A[i], 0);
        }
    
        int max = 0;
    
        for(int i = 1; i < A.Length - 1; i++) {
            max = Math.Max(max, s1Max[i - 1] + s2Max[i + 1]);
        }
    
        return max;
    }
}