// Task description

// You are given a record of the historical prices of an investment asset from the last N days. Analyze the record in order to calculate what could have been your maximum income. Assume you started with one asset of this type and could hold at most one at a time. You could choose to sell the asset whenever you held one. If you did not hold an asset at some moment, you could always afford to buy an asset (assume you had infinite money available).

// What is the maximum income you could make?

// Write a function:

// int solution(int A[], int N);

// that, given an array A of length N representing a record of prices over the last N days, returns the maximum income you could make. As the result may be large, return its last nine digits without leading zeros (return the result modulo 1,000,000,000).

// Examples:

​

// Given A = [4, 1, 2, 3], the function should return 6. You could sell the product on the first day (for 4), buy it on the second (for 1) and sell it again on the last day (for 3). The income would be equal 4 - 1 + 3 = 6.

// Given A = [1, 2, 3, 3, 2, 1, 5], the function should return 7. You could sell the product when its value was 3, buy it when it changed to 1, and sell it again when it was worth 3.

// Given A = [1000000000, 2, 2, 2, 1000000000, 1, 1000000000], the function should return 999999997. The maximum possible income is 2999999997, whose last 9 digits are 999999997.

// Write an efficient algorithm for the following assumptions:

// • N is an integer within the range [1, 200,000];

// • each element of array A is an integer within the range [0, 1,000,000,000].

​

using System;

public class Program

{

    public static void Main(string[] args)

    {

        int[] A = new int[] {4, 1, 2, 3};

        var solutionA = Solution(A, A.Length);

        int[] B = new int[] {1, 2, 3, 3, 2, 1, 5};

        var solutionB = Solution(B, B.Length);

        int[] C = new int[] {1000000000, 2, 2, 2, 1000000000, 1, 1000000000};

        var solutionC = Solution(C, C.Length);

        Console.WriteLine("{0}, {1}, {2}", solutionA, solutionB, solutionC);

    }

    private static int Solution(int[] A, int N)

    {

        // Write your code here :)

        return 0;

    }

}