Broad Network


MaxProfit at app.codility.com/programmers in PHP Explained: Given a log of stock prices compute the maximum possible earning.

Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)
Lesson 9 at app.codility.com/programmers
The solution and its explanation are given below.

Category of Article : Technology | Computers and Software | Algorithm

By: Chrysanthus Date Published: 30 Jul 2025

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,

    function solution($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].

Note:

The N consecutive days have passed.

For any profit, a number ahead in the array must subtract a number behind in the array, and the answer should be positive. 

The maximum profit has been asked for. So comparison of slice sums (from the lesson) is not needed. So Kadane’s algorithm for maximum slice sum is not directly or wholly needed here.

No particular loss has been asked for. If 0 profit or no profit (all losses) was made, 0 is returned.  

Strategy

Since one particular share price ahead must subtract one particular share price behind, then there should be a running maximum particular share price, which is assumed to be the greatest maximum share price. For maximum profit, the subtraction is between the greatest share price ahead and the least share price behind. As the given array is scanned from the beginning to the end, these values are looked for, while subtraction is being made to obtain the maximum profit.

In the code below, scanning begins from i = 1 and not i = 0. A[i] is assumed to be the maximum particular running share price. A[0] is the first minimum share price on the left (assumed). As the given array is scanned, there is a minimum particular running share price, the first of which is A[0] (assumed). Still as the given array is scanned, subtraction is taking place between the running maximum price and the running minimum price, and comparison of the differences are obtained progressively. All those calculations take place in one body of the for-loop, leading to O(n) time.

Smart Solution

The solution() function is in the following program (read the code and comments). The running maximum share price is A[i]. 
<?php
function solution($A) {
    $N = count($A);
    if ($N<=1) return 0;  // A[i] - A[i] = 0; needs at least two elements, for comparison 

    $maxDiff = 0;
    $minValue = $A[0];

    for ($i=1; $i < $N; $i++) {
        if ($A[$i] < $minValue) 
            $minValue = $A[$i];

        if (($A[$i] - $minValue) > $maxDiff)    //cannot be greater than 0 if indexes are the same
            $maxDiff = $A[$i] - $minValue;
    }

    if ($maxDiff <= 0)   //losses were never calculated
        return 0;

    return $maxDiff;
}

$B = [23171, 21011, 21123, 21366, 21013, 21367];
$ret = solution($B);
echo $ret . "\n";

$C = [8, 9, 3, 6, 1, 2];
$ret1 = solution($C);
echo $ret1 . "\n";
?>
The maximum running share price is implicit. The output is:

    356
    3

The two if-statements in the for-loop body, are not really connected. They are independent. They do not form an if/else construct. 

At app.codility.com/programmers the scoring and detected time complexity for this solution() is:

    Task score : 100% -  Correctness : 100% ; Performance : 100%
    Detected time complexity : O(N)

Thanks for reading.

The rest of the 17 lessons, with explanation of lessons, explanation of tasks, and explanation of solutions, can be found at (click): Explanations in PHP for the 17 Algorithm Lessons at https://app.codility.com/programmers with Problems and Solutions





Related Links

Basics of PHP with Security Considerations
White Space in PHP
PHP Data Types with Security Considerations
PHP Variables with Security Considerations
PHP Operators with Security Considerations
PHP Control Structures with Security Considerations
PHP String with Security Considerations
PHP Arrays with Security Considerations
PHP Functions with Security Considerations
PHP Return Statement
Exception Handling in PHP
Variable Scope in PHP
Constant in PHP
PHP Classes and Objects
Reference in PHP
PHP Regular Expressions with Security Considerations
Date and Time in PHP with Security Considerations
Files and Directories with Security Considerations in PHP
Writing a PHP Command Line Tool
PHP Core Number Basics and Testing
Validating Input in PHP
PHP Eval Function and Security Risks
PHP Multi-Dimensional Array with Security Consideration
Mathematics Functions for Everybody in PHP
PHP Cheat Sheet and Prevention Explained
More Related Links

Cousins

BACK NEXT

Comments