Tag buy sell stock

Stock Buy and Sell – Multiple Transactions Allowed in C: A Comprehensive Tutorial

The Stock Buy and Sell problem with multiple transactions allowed is a classic algorithmic problem that tests your understanding of greedy algorithms, array traversal, and profit accumulation. Given an array of stock prices, the goal is to find the maximum total profit by buying and selling the stock any number of times.

This tutorial provides an in-depth exploration of this problem: naive recursive approach, local minima/maxima approach, profit accumulation approach, practical implementation, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is the Problem?

Given an array prices[] representing daily stock prices, find the maximum total profit that can be earned by buying and selling the stock any number of times.

Constraints:

• We can only sell a stock we have bought earlier.
• We cannot hold multiple stocks simultaneously.
• We can perform as many transactions as we want.

Example:

text

Input: prices = [100, 180, 260, 310, 40, 535, 695] Output: 865 Explanation: Buy at 100, sell at 310 → Profit = 210 Buy at 40, sell at 695 → Profit = 655 Total = 865

Why This Problem Matters

• Greedy algorithm design: Demonstrates optimal substructure.
• Profit accumulation: Foundation for financial algorithms.
• Array traversal: Practical application of scanning patterns.
• Interview preparation: Very common coding interview question.
• Real-world applications: Trading strategies, resource allocation.

Key Insight

Profit is earned whenever the price rises from one day to the next. We can capture every upward movement by accumulating the differences between adjacent days where prices increase.

Formula:

text

Total Profit = Σ max(0, prices[i] - prices[i-1]) for i = 1 to n-1

Approaches Overview

Approach	Time Complexity	Space Complexity
Naive recursion	O(2^n)	O(n)
Local minima/maxima	O(n)	O(1)
Profit accumulation	O(n)	O(1)

---

Syntax & Core Mechanics

Approach 1: Naive Recursive (Try All Possibilities)

Try every pair of buy/sell days recursively.

c

#include <stdio.h> #include <limits.h> int maxProfitRec(const int prices[], int start, int end) { if (start >= end) return 0; int res = 0; for (int i = start; i < end; i++) { for (int j = i + 1; j <= end; j++) { if (prices[j] > prices[i]) { int curr = (prices[j] - prices[i]) + maxProfitRec(prices, start, i - 1) + maxProfitRec(prices, j + 1, end); if (curr > res) res = curr; } } } return res; } int maxProfitNaive(const int prices[], int n) { return maxProfitRec(prices, 0, n - 1); } int main(void) { int prices[] = {100, 180, 260, 310, 40, 535, 695}; int n = sizeof(prices) / sizeof(prices[0]); printf("Maximum profit: %d\n", maxProfitNaive(prices, n)); return 0; }

Expected output:

text

Maximum profit: 865

Time: O(2^n), Space: O(n)

Approach 2: Local Minima and Maxima

Find local minima (buy points) and local maxima (sell points).

c

#include <stdio.h> int maxProfitLocalMinMax(const int prices[], int n) { if (n <= 1) return 0; int res = 0; int i = 0; while (i < n - 1) { /* Find local minima */ while (i < n - 1 && prices[i] >= prices[i + 1]) { i++; } int lMin = prices[i]; /* Find local maxima */ while (i < n - 1 && prices[i] <= prices[i + 1]) { i++; } int lMax = prices[i]; res += (lMax - lMin); } return res; } int main(void) { int prices[] = {100, 180, 260, 310, 40, 535, 695}; int n = sizeof(prices) / sizeof(prices[0]); printf("Maximum profit: %d\n", maxProfitLocalMinMax(prices, n)); return 0; }

Expected output:

text

Maximum profit: 865

Time: O(n), Space: O(1)

Approach 3: Profit Accumulation (Simplest and Optimal)

Add every positive difference between adjacent days.

c

#include <stdio.h> int maxProfit(const int prices[], int n) { if (n <= 1) return 0; int res = 0; for (int i = 1; i < n; i++) { if (prices[i] > prices[i - 1]) { res += prices[i] - prices[i - 1]; } } return res; } int main(void) { int prices[] = {100, 180, 260, 310, 40, 535, 695}; int n = sizeof(prices) / sizeof(prices[0]); printf("Maximum profit: %d\n", maxProfit(prices, n)); return 0; }

Expected output:

text

Maximum profit: 865

Time: O(n), Space: O(1)

Why Accumulation Works

Buying at a valley and selling at a peak is equivalent to capturing every small upward move between them.

text

Prices: [100, 180, 260, 310] Buy at 100, sell at 310 = 210 Accumulate: (180-100) + (260-180) + (310-260) = 80 + 80 + 50 = 210 ✓

---

Full Practical Code Example with Explanation

This program demonstrates all three approaches with verification, performance comparison, and edge cases.

Program: Stock Profit Maximizer

c

/** * stock_profit.c * Finds maximum profit with multiple stock transactions. * Compares naive, local min/max, and accumulation approaches. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 /* Function prototypes */ int maxProfitNaive(const int prices[], int n); int maxProfitRec(const int prices[], int start, int end); int maxProfitLocalMinMax(const int prices[], int n); int maxProfitAccumulate(const int prices[], int n); int readInteger(const char *prompt, int *outValue); void printArray(const int prices[], int n); void demonstrateApproaches(void); void performanceComparison(void); void demonstrateEdgeCases(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Stock Buy and Sell (Multiple Transactions) ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate All Approaches\n"); printf("2. Custom Prices\n"); printf("3. Performance Comparison\n"); printf("4. Edge Cases\n"); printf("5. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demonstrateApproaches(); break; case 2: { int prices[MAX_SIZE]; int n; if (readInteger("Enter number of days (1-100000): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 1 || n > MAX_SIZE) { printf("Size must be 1-%d.\n", MAX_SIZE); break; } printf("Enter %d prices:\n", n); for (int i = 0; i < n; i++) { char prompt[50]; snprintf(prompt, sizeof(prompt), " Day %d price: ", i); if (readInteger(prompt, &prices[i]) != 0) { fprintf(stderr, "Invalid input.\n"); n = i; break; } } printf("\nPrices: "); printArray(prices, n); int result = maxProfitAccumulate(prices, n); printf("Maximum profit: %d\n", result); break; } case 3: performanceComparison(); break; case 4: demonstrateEdgeCases(); break; case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Naive recursive helper */ int maxProfitRec(const int prices[], int start, int end) { if (start >= end) return 0; int res = 0; for (int i = start; i < end; i++) { for (int j = i + 1; j <= end; j++) { if (prices[j] > prices[i]) { int curr = (prices[j] - prices[i]) + maxProfitRec(prices, start, i - 1) + maxProfitRec(prices, j + 1, end); if (curr > res) res = curr; } } } return res; } /* Naive approach */ int maxProfitNaive(const int prices[], int n) { if (n <= 1) return 0; return maxProfitRec(prices, 0, n - 1); } /* Local minima/maxima approach */ int maxProfitLocalMinMax(const int prices[], int n) { if (n <= 1) return 0; int res = 0; int i = 0; while (i < n - 1) { while (i < n - 1 && prices[i] >= prices[i + 1]) i++; int lMin = prices[i]; while (i < n - 1 && prices[i] <= prices[i + 1]) i++; int lMax = prices[i]; res += (lMax - lMin); } return res; } /* Accumulation approach */ int maxProfitAccumulate(const int prices[], int n) { if (n <= 1) return 0; int res = 0; for (int i = 1; i < n; i++) { if (prices[i] > prices[i - 1]) { res += prices[i] - prices[i - 1]; } } return res; } /* Prints array */ void printArray(const int prices[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", prices[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Demonstrates all approaches */ void demonstrateApproaches(void) { printf("\n=== Sample Arrays ===\n"); int prices1[] = {100, 180, 260, 310, 40, 535, 695}; int n1 = sizeof(prices1) / sizeof(prices1[0]); printf("\nPrices 1: "); printArray(prices1, n1); printf("Naive: %d\n", maxProfitNaive(prices1, n1)); printf("MinMax: %d\n", maxProfitLocalMinMax(prices1, n1)); printf("Accumulate: %d\n", maxProfitAccumulate(prices1, n1)); int prices2[] = {4, 2}; int n2 = sizeof(prices2) / sizeof(prices2[0]); printf("\nPrices 2: "); printArray(prices2, n2); printf("Naive: %d\n", maxProfitNaive(prices2, n2)); printf("MinMax: %d\n", maxProfitLocalMinMax(prices2, n2)); printf("Accumulate: %d\n", maxProfitAccumulate(prices2, n2)); int prices3[] = {1, 2, 3, 4, 5}; int n3 = sizeof(prices3) / sizeof(prices3[0]); printf("\nPrices 3 (increasing): "); printArray(prices3, n3); printf("Naive: %d\n", maxProfitNaive(prices3, n3)); printf("MinMax: %d\n", maxProfitLocalMinMax(prices3, n3)); printf("Accumulate: %d\n", maxProfitAccumulate(prices3, n3)); int prices4[] = {5, 4, 3, 2, 1}; int n4 = sizeof(prices4) / sizeof(prices4[0]); printf("\nPrices 4 (decreasing): "); printArray(prices4, n4); printf("Naive: %d\n", maxProfitNaive(prices4, n4)); printf("MinMax: %d\n", maxProfitLocalMinMax(prices4, n4)); printf("Accumulate: %d\n", maxProfitAccumulate(prices4, n4)); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison ===\n"); /* Naive is only feasible for small arrays */ int smallSize = 15; int *smallArr = malloc(smallSize * sizeof(int)); if (smallArr == NULL) return; srand(42); for (int i = 0; i < smallSize; i++) { smallArr[i] = rand() % 100 + 1; } clock_t start, end; double timeTaken; start = clock(); int naiveResult = maxProfitNaive(smallArr, smallSize); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Naive (n=%d, O(2^n)): Result = %d, Time = %.3f ms\n", smallSize, naiveResult, timeTaken); free(smallArr); /* Larger arrays for efficient approaches */ int largeSize = 100000; int *largeArr = malloc(largeSize * sizeof(int)); if (largeArr == NULL) return; for (int i = 0; i < largeSize; i++) { largeArr[i] = rand() % 1000 + 1; } start = clock(); int minMaxResult = maxProfitLocalMinMax(largeArr, largeSize); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("MinMax (n=%d, O(n)): Result = %d, Time = %.3f ms\n", largeSize, minMaxResult, timeTaken); start = clock(); int accResult = maxProfitAccumulate(largeArr, largeSize); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Accumulate (n=%d, O(n)): Result = %d, Time = %.3f ms\n", largeSize, accResult, timeTaken); printf("\nVerification (MinMax vs Accumulate): %s\n", (minMaxResult == accResult) ? "PASS" : "FAIL"); free(largeArr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Case 1: Empty array */ int prices1[] = {}; printf("Case 1: Empty array\n"); printf(" Profit: %d\n", maxProfitAccumulate(prices1, 0)); /* Case 2: Single day */ int prices2[] = {42}; printf("\nCase 2: Single day\n"); printf(" Prices: "); printArray(prices2, 1); printf(" Profit: %d\n", maxProfitAccumulate(prices2, 1)); /* Case 3: Two days, profit possible */ int prices3[] = {5, 10}; printf("\nCase 3: Two days, profit possible\n"); printf(" Prices: "); printArray(prices3, 2); printf(" Profit: %d\n", maxProfitAccumulate(prices3, 2)); /* Case 4: Two days, no profit */ int prices4[] = {10, 5}; printf("\nCase 4: Two days, no profit\n"); printf(" Prices: "); printArray(prices4, 2); printf(" Profit: %d\n", maxProfitAccumulate(prices4, 2)); /* Case 5: All same prices */ int prices5[] = {7, 7, 7, 7}; printf("\nCase 5: All same prices\n"); printf(" Prices: "); printArray(prices5, 4); printf(" Profit: %d\n", maxProfitAccumulate(prices5, 4)); /* Case 6: Zigzag prices */ int prices6[] = {10, 5, 15, 8, 20}; printf("\nCase 6: Zigzag prices\n"); printf(" Prices: "); printArray(prices6, 5); printf(" Profit: %d\n", maxProfitAccumulate(prices6, 5)); /* Case 7: Large price differences */ int prices7[] = {1, 10000, 1, 10000}; printf("\nCase 7: Large price differences\n"); printf(" Prices: "); printArray(prices7, 4); printf(" Profit: %d (watch for overflow)\n", maxProfitAccumulate(prices7, 4)); } /* Reads an integer safely */ int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { return -1; } errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) { return -1; } if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) { return -1; } *outValue = (int)val; return 0; }

Explanation of Approaches

1. Naive: Tries all buy/sell pairs recursively; O(2^n).
2. Local Min/Max: Finds valleys and peaks; O(n).
3. Accumulation: Adds all positive adjacent differences; O(n) — simplest and optimal.

Expected Output (sample run)

text

=== Stock Buy and Sell (Multiple Transactions) === --- Menu --- 1. Demonstrate All Approaches 2. Custom Prices 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === Sample Arrays === Prices 1: [100, 180, 260, 310, 40, 535, 695] Naive: 865 MinMax: 865 Accumulate: 865 Prices 2: [4, 2] Naive: 0 MinMax: 0 Accumulate: 0 Prices 3 (increasing): [1, 2, 3, 4, 5] Naive: 4 MinMax: 4 Accumulate: 4 Prices 4 (decreasing): [5, 4, 3, 2, 1] Naive: 0 MinMax: 0 Accumulate: 0 --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: Empty array Profit: 0 Case 2: Single day Prices: [42] Profit: 0 Case 3: Two days, profit possible Prices: [5, 10] Profit: 5 Case 4: Two days, no profit Prices: [10, 5] Profit: 0 Case 5: All same prices Prices: [7, 7, 7, 7] Profit: 0 Case 6: Zigzag prices Prices: [10, 5, 15, 8, 20] Profit: 22 Case 7: Large price differences Prices: [1, 10000, 1, 10000] Profit: 19998 (watch for overflow)

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Integer Overflow

Total profit can exceed int for large arrays with big price differences.

c

long long profit = 0; /* Use long long for safety */

2. Empty Array

Return 0 for empty or single-element arrays.

c

if (n <= 1) return 0;

3. Decreasing Prices

No profit possible; return 0.

c

int prices[] = {5, 4, 3, 2, 1}; /* Profit = 0 */

4. All Same Prices

No profit; return 0.

c

int prices[] = {7, 7, 7, 7}; /* Profit = 0 */

5. Holding Multiple Stocks

Problem prohibits holding multiple stocks; accumulation approach respects this.

6. Selling Before Buying

The accumulation approach naturally only counts upward moves, respecting buy-before-sell.

7. Using Naive for Large Arrays

Naive O(2^n) is only feasible for n ≤ 20.

Solution: Use O(n) approaches.

8. Off-by-One in Loops

The accumulation loop starts at i = 1 (comparing with i-1).

c

for (int i = 1; i < n; i++) { ... } /* Correct */

9. Local Min/Max Edge Cases

Ensure the while loops terminate correctly at array boundaries.

10. Memory Considerations

• Naive: O(n) stack space due to recursion.
• MinMax: O(1) extra space.
• Accumulate: O(1) extra space — preferred.
• Use long long for profit on large inputs.

---

Summary & Best Practices

The Stock Buy and Sell problem with multiple transactions is elegantly solved by accumulating all positive adjacent price differences. This captures every profitable opportunity in O(n) time and O(1) space.

Key Takeaways

• Profit comes from upward price movements.
• Accumulate all positive prices[i] - prices[i-1].
• Naive: O(2^n) time.
• MinMax: O(n) time.
• Accumulate: O(n) time, O(1) space — simplest and optimal.
• Use long long for large profits.

Best Practices

1. Use the accumulation approach for O(n) time and O(1) space.
2. Use long long for profit to prevent overflow.
3. Handle edge cases: empty, single element, decreasing, all same.
4. Verify with local min/max during testing.
5. Avoid naive recursion for large arrays.
6. Document the greedy insight in comments.
7. Validate input (array size, values).
8. Test with zigzag patterns and large differences.
9. Use const for input arrays.
10. Profile for large arrays.

By mastering this problem, you’ll understand greedy accumulation and be prepared for related financial and optimization problems.