MaxProfit

Given a log of stock prices compute the maximum possible earning
ℹ️ © Codility, 2009-2018

Problem

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 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.

Assume that:
• n is an integer within the range [0 … 400,000];
• each element of array A is an integer within the range [0 … 200,000].

Complexity:
• expected worst-case time complexity is O(n);
• expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Solution

C#

using System;
class Solution {
  public int solution(int[] A) {
    int t = 0;
    int r = 0;
    int n = A.Length;
    for (int i = 1; i < n; i++) {
      t = Math.Max(0, t + A[i] - A[i - 1]);
      r = Math.Max(r, t);
    }
    return r > 0 ? r : 0;
  }
}

Java

import java.lang.Math;
class Solution {
  public int solution(int[] A) {
    int t = 0;
    int r = 0;
    int n = A.length;
    for (int i = 1; i < n; i++) {
      t = Math.max(0, t + A[i] - A[i - 1]);
      r = Math.max(r, t);
    }
    return r > 0 ? r : 0;
  }
}

JavaScript

function solution(A) {
  let t = 0;
  let r = 0;
  let n = A.length;
  for (let i = 1; i < n; i++) {
    t = Math.max(0, t + A[i] - A[i - 1]);
    r = Math.max(r, t);
  }
  return r > 0 ? r : 0;
}

PHP

function solution($A) {
  $t = 0;
  $r = 0;
  $n = count($A);
  for ($i = 1; $i < $n; $i++) {
    $t = max(0, $t + $A[$i] - $A[$i - 1]);
    $r = max($r, $t);
  }
  return $r > 0 ? $r : 0;
}