1class BinaryIndexedTree {
2    private int size;
3    private int[] tree;
4
5    // Construct a Binary Indexed Tree with given size
6    public BinaryIndexedTree(int size) {
7        this.size = size;
8        tree = new int[size + 1];
9    }
10
11    // Update the Binary Indexed Tree at index `index` with value `value`
12    // using point update operation where each node stores the maximum value
13    public void update(int index, int value) {
14        while (index <= size) {
15            tree[index] = Math.max(tree[index], value);
16            index += index & -index;
17        }
18    }
19
20    // Query the maximum value in the range [1, index]
21    public int query(int index) {
22        int max = 0;
23        while (index > 0) {
24            max = Math.max(max, tree[index]);
25            index -= index & -index;
26        }
27        return max;
28    }
29}
30
31class Solution {
32    // Calculate the maximum profit that can be obtained by buying and selling the 
33    // items given the prices and profits of each item
34    public int maxProfit(int[] prices, int[] profits) {
35        int n = prices.length;
36        int maxPrice = 0;
37      
38        // Track the prefix maximum profit from left and right
39        int[] prefixMaxLeft = new int[n];
40        int[] prefixMaxRight = new int[n];
41      
42        // Find out the maximum price for item initialization
43        for (int price : prices) {
44            maxPrice = Math.max(maxPrice, price);
45        }
46      
47        // Initialize two Binary Indexed Trees
48        BinaryIndexedTree treeFromLeft = new BinaryIndexedTree(maxPrice + 1);
49        BinaryIndexedTree treeFromRight = new BinaryIndexedTree(maxPrice + 1);
50      
51        // Scan from left to right and update prefixMaxLeft with the maximum profit seen so far
52        for (int i = 0; i < n; ++i) {
53            int price = prices[i];
54            prefixMaxLeft[i] = treeFromLeft.query(price - 1);
55            treeFromLeft.update(price, profits[i]);
56        }
57      
58        // Scan from right to left and update prefixMaxRight with the maximum profit seen so far
59        for (int i = n - 1; i >= 0; --i) {
60            // Invert price to keep the non-decreasing order when scanning from right to left
61            int invertedPrice = maxPrice + 1 - prices[i];
62            prefixMaxRight[i] = treeFromRight.query(invertedPrice - 1);
63            treeFromRight.update(invertedPrice, profits[i]);
64        }
65      
66        // Calculate the maximum profit by taking the max of the profit obtainable at each index
67        int maxProfit = -1; // Initialize it to -1 to represent no valid transaction performed
68        for (int i = 0; i < n; ++i) {
69            if (prefixMaxLeft[i] > 0 && prefixMaxRight[i] > 0) {
70                maxProfit = Math.max(maxProfit, prefixMaxLeft[i] + profits[i] + prefixMaxRight[i]);
71            }
72        }
73      
74        return maxProfit;
75    }
76}
77

1#include <vector>
2#include <algorithm>
3using namespace std;
4
5// Class for the Binary Indexed Tree (BIT), also known as Fenwick Tree.
6class BinaryIndexedTree {
7private:
8    int size;              // The size of the original array
9    vector<int> tree;      // The array representation of the binary indexed tree
10
11public:
12    // Constructor initializes the BIT with the given size.
13    explicit BinaryIndexedTree(int size) {
14        this->size = size;
15        tree.resize(size + 1, 0);
16    }
17
18    // Updates the BIT with a value 'v' at index 'index'.
19    void update(int index, int value) {
20        while (index <= size) {
21            tree[index] = max(tree[index], value); // Store the maximum value up to the current index
22            index += index & -index;              // Move to the parent node in the update viewpoint
23        }
24    }
25
26    // Queries the maximum value in the BIT up to index 'index'.
27    int query(int index) {
28        int maxVal = 0;
29        while (index > 0) {
30            maxVal = max(maxVal, tree[index]);   // Obtain the maximum value from the tree
31            index -= index & -index;             // Move to the parent node in the query viewpoint
32        }
33        return maxVal;
34    }
35};
36
37// The Solution class contains the method to determine the maximum profit.
38class Solution {
39public:
40    // Calculates the maximum profit for buying and selling stocks.
41    int maxProfit(vector<int>& prices, vector<int>& profits) {
42        int itemCount = prices.size();                             // The number of items
43        vector<int> leftMaxProfit(itemCount, 0);                  // Max profit to the left of an index
44        vector<int> rightMaxProfit(itemCount, 0);                 // Max profit to the right of an index
45        int maxPrice = *max_element(prices.begin(), prices.end()); // Maximum price to determine BIT size
46      
47        BinaryIndexedTree treeBefore(maxPrice + 1);
48        BinaryIndexedTree treeAfter(maxPrice + 1);
49      
50        // Calculate the maximum profit before each index
51        for (int i = 0; i < itemCount; ++i) {
52            int currentPrice = prices[i];
53            leftMaxProfit[i] = treeBefore.query(currentPrice - 1);
54            treeBefore.update(currentPrice, profits[i]);
55        }
56      
57        // Calculate the maximum profit after each index
58        for (int i = itemCount - 1; i >= 0; --i) {
59            int adjustedPrice = maxPrice + 1 - prices[i];
60            rightMaxProfit[i] = treeAfter.query(adjustedPrice - 1);
61            treeAfter.update(adjustedPrice, profits[i]);
62        }
63      
64        // Find the maximum profit that can be achieved by buying and selling a stock
65        int maxTotalProfit = -1; // Initialize with -1 to represent no transaction
66        for (int i = 0; i < itemCount; ++i) {
67            if (leftMaxProfit[i] > 0 && rightMaxProfit[i] > 0) { // Check if a profit can be made at current index
68                maxTotalProfit = max(maxTotalProfit, leftMaxProfit[i] + profits[i] + rightMaxProfit[i]);
69            }
70        }
71        return maxTotalProfit;  // Return the maximum profit found
72    }
73};
74

1// Constants representing the size of the binary indexed tree (BIT)
2let treeSize: number;
3let treeArray: number[];
4
5// Initialize the data structure for BIT with a specified size
6function init(n: number): void {
7    treeSize = n;
8    treeArray = Array(n + 1).fill(0);
9}
10
11// Update the BIT with a value at a specific index
12function update(index: number, value: number): void {
13    while (index <= treeSize) {
14        // We use the max operation for this update as per the problem's requirements
15        treeArray[index] = Math.max(treeArray[index], value);
16        // Move to the next index to be updated
17        index += index & -index;
18    }
19}
20
21// Query the BIT to find the maximum value up to a certain index
22function query(index: number): number {
23    let maxVal = 0;
24    while (index > 0) {
25        maxVal = Math.max(maxVal, treeArray[index]);
26        // Move to the next index to continue the query
27        index -= index & -index;
28    }
29    return maxVal;
30}
31
32// Function to calculate the max profit from price and profit arrays
33function maxProfit(prices: number[], profits: number[]): number {
34    const n = prices.length;
35    const maxPrice = Math.max(...prices); // Get the maximum price for the BIT size
36
37    init(maxPrice + 1); // Initialize the BIT with the size of the maximum price + 1
38
39    let leftMaxes = Array(n).fill(0); // Array to store the max profit up to the current price from the left
40    let rightMaxes = Array(n).fill(0); // Array to store the max profit up to the current price from the right
41
42    // Build the BIT from the left for each price and keep track of maximum profit at each point
43    for (let i = 0; i < n; i++) {
44        const currentPrice = prices[i];
45        leftMaxes[i] = query(currentPrice - 1); // Current max profit before this price
46        update(currentPrice, profits[i]); // Update the BIT with the current profit
47    }
48
49    init(maxPrice + 1); // Reinitialize the BIT for right side calculations
50
51    // Build the BIT from the right for each price and keep track of maximum profit at each point
52    for (let i = n - 1; i >= 0; i--) {
53        const currentPrice = maxPrice + 1 - prices[i];
54        rightMaxes[i] = query(currentPrice - 1); // Current max profit before this price from the right
55        update(currentPrice, profits[i]); // Update the BIT with the current profit
56    }
57
58    let maxProfit = -1; // Initialize maxProfit with -1 assuming no transaction is done
59
60    // For each price point, calculate the maximum profit if purchased and sold at that price
61    for (let i = 0; i < n; i++) {
62        if (leftMaxes[i] > 0 && rightMaxes[i] > 0) {
63            maxProfit = Math.max(maxProfit, leftMaxes[i] + profits[i] + rightMaxes[i]);
64        }
65    }
66
67    return maxProfit; // Return the maximum achievable profit
68}
69