Maximize Portfolio Value

Overview

The problem asks us to maximize the future value of a portfolio given a budget $m$ and a set of securities. Each security has a current price, a predicted future price, and a purchasing limit. Key to this problem is the fact that fractional shares are allowed.

In financial optimization, when you can buy fractional amounts of an item to maximize a linear gain (the future value), a greedy approach is almost always optimal. We want to prioritize securities that give us the "most bang for our buck"—essentially, the highest return on investment (ROI).

If a security's future price is lower than or equal to its current price, it offers a neutral or negative return. Since cash maintains its value ($1 today = $1 tomorrow), we should never buy such a security.

Brute Force

A "brute force" approach in this context might involve simply iterating through the list and buying as much as possible of the first security we see, then the second, and so on. however, this is suboptimal because it doesn't account for the potential returns.

To make it slightly more exhaustive without being "optimal," one might try to generate different permutations of the purchase order, but given the constraints and the nature of fractional shares (Continuous Knapsack Problem), the greedy choice is mathematically guaranteed to be part of the optimal solution.

Below is a basic implementation that filters for profitable stocks but doesn't necessarily pick the best ones first.

def maximize_portfolio_value(m: int, sec: list[list[str]]) -> float:
    total_future_value = 0.0
    remaining_cash = float(m)
    
    # Simple iteration without optimal sorting
    for s in sec:
        name, p_str, s_str, a_str = s
        p, s_val, a = float(p_str), float(s_str), float(a_str)
        
        # Only consider if it's profitable
        if s_val > p:
            # Buy as much as possible (limited by A_i and remaining cash)
            can_afford = remaining_cash / p
            amount_to_buy = min(can_afford, a)
            
            remaining_cash -= amount_to_buy * p
            total_future_value += amount_to_buy * s_val
            
    return total_future_value + remaining_cash

• Time complexity: O(N) — We iterate through the list of securities once.
• Space complexity: O(1) — We only store a few scalar variables regardless of input size.

Optimal / Best Approach

The optimal strategy is a Greedy Algorithm based on the Return Ratio. This is a variation of the Fractional Knapsack Problem.

1. Calculate the Ratio: For every security where $S_i > P_i$, calculate the ratio $R_i = S_i / P_i$. This represents how many dollars we get in the future for every $1 spent today.
2. Sort: Sort the profitable securities in descending order based on their ratio $R_i$.
3. Greedy Purchase: - Start with the security offering the highest ratio.
   • Buy the maximum allowed amount ($A_i$), or as much as your current cash allows.
   • Move to the next best security until your cash is exhausted or you have bought all profitable securities.
4. Cash Preservation: Any cash that cannot be invested in a profitable security ($S_i > P_i$) is kept as cash, contributing 1:1 to the future value.

def maximize_portfolio_value(m: int, sec: list[list[str]]) -> float:
    # 1. Parse and filter for profitable securities
    profitable_secs = []
    for s in sec:
        name, p_curr_str, p_future_str, amt_max_str = s
        p_curr = float(p_curr_str)
        p_future = float(p_future_str)
        amt_max = float(amt_max_str)
        
        if p_future > p_curr:
            # We store the return ratio (future/current) to sort by
            ratio = p_future / p_curr
            profitable_secs.append({
                'ratio': ratio,
                'p_curr': p_curr,
                'p_future': p_future,
                'amt_max': amt_max
            })
            
    # 2. Sort by return ratio descending
    profitable_secs.sort(key=lambda x: x['ratio'], reverse=True)
    
    current_cash = float(m)
    total_future_value = 0.0
    
    # 3. Greedy allocation
    for s in profitable_secs:
        if current_cash <= 0:
            break
            
        # How many shares can we buy with available cash?
        shares_we_can_buy = current_cash / s['p_curr']
        # Limited by the maximum allowed shares
        actual_buy = min(shares_we_can_buy, s['amt_max'])
        
        current_cash -= (actual_buy * s['p_curr'])
        total_future_value += (actual_buy * s['p_future'])
        
    # 4. Add remaining cash (which didn't lose value)
    return total_future_value + current_cash

• Time complexity: O(N log N) — The bottleneck is sorting the list of $N$ securities by their return ratio.
• Space complexity: O(N) — We store the filtered list of profitable securities before sorting.

Why this works

Because we are allowed to buy fractional shares, the problem does not suffer from the "item fit" issues seen in the 0/1 Knapsack problem (which requires Dynamic Programming). Since every dollar spent on a higher-ratio security yields more future value than a dollar spent on a lower-ratio security, it is always mathematically optimal to exhaust the best options first.

Fast