Best Time to Buy and Sell Stock - C Solution

1. Introduction

This blog post discusses a common problem in financial computing and array manipulation using C programming - finding the best time to buy and sell stock for maximum profit. This problem is a classic example of understanding how to efficiently navigate arrays to find optimal solutions, a key skill in algorithmic trading and financial analysis.

Problem

Given an array prices where prices[i] represents the price of a given stock on the ith day, the task is to find the maximum profit that can be achieved from a single transaction. This involves choosing the best day to buy and the best day in the future to sell the stock. If no profit can be made, the function should return 0.

2. Solution Steps

1. Initialize a variable minPrice to represent the minimum price seen so far and maxProfit to represent the maximum profit that can be achieved.

2. Iterate through the prices array.

3. Update minPrice if a lower price is found.

4. Calculate the profit for each day by subtracting the minPrice from the current price and update maxProfit if a higher profit is found.

5. Return the maxProfit.

3. Code Program

#include <stdio.h>
#include <limits.h>

// Function to find the maximum profit
int maxProfit(int* prices, int pricesSize) {
    int minPrice = INT_MAX; // Initialize minPrice with maximum possible integer value
    int maxProfit = 0;      // Initialize maxProfit as 0

    // Loop through each price
    for (int i = 0; i < pricesSize; i++) {
        // Update minPrice if a lower price is found
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        }
        // Update maxProfit if a higher profit can be made
        else if (prices[i] - minPrice > maxProfit) {
            maxProfit = prices[i] - minPrice;
        }
    }
    return maxProfit; // Return the maximum profit found
}

// Main function to test the maxProfit function
int main() {
    int prices1[] = {7, 1, 5, 3, 6, 4};
    int pricesSize1 = sizeof(prices1) / sizeof(prices1[0]);
    printf("Maximum Profit (Example 1): %d\n", maxProfit(prices1, pricesSize1));

    int prices2[] = {7, 6, 4, 3, 1};
    int pricesSize2 = sizeof(prices2) / sizeof(prices2[0]);
    printf("Maximum Profit (Example 2): %d\n", maxProfit(prices2, pricesSize2));

    return 0;
}

Output:

Maximum Profit (Example 1): 5
Maximum Profit (Example 2): 0

Explanation:

1. int minPrice = INT_MAX; int maxProfit = 0; - Initialize minPrice and maxProfit.

2. for (int i = 0; i < pricesSize; i++) - Iterate through each price.

3. if (prices[i] < minPrice) - Update minPrice if a lower price is found.

4. else if (prices[i] - minPrice > maxProfit) - Calculate profit and update maxProfit if this profit is greater than the current maxProfit.

5. return maxProfit; - Return the maximum profit that can be made.

6. The main function tests the maxProfit function with two examples and prints the maximum profit for each.