Maximum value of k coins from piles

Array Dynamic Programming Prefix Sum

60.4% acceptance

Feb 25, 2026

2442

There are n piles of coins on a table. Each pile consists of a positive number of coins of assorted denominations. In one move, you can choose any coin on top of any pile, remove it, and add it to your wallet. Given a list piles, where piles[i] is a list of integers denoting the composition of the ith pile from top to bottom, and a positive integer k, return the maximum total value of coins you can have in your wallet if you choose exactly k coins optimally.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_value_of_coins(piles: Vec<Vec<i32>>, k: i32) -> i32 {
    let k = k as usize;
    // dp[j] = max value using exactly j coins from first i piles
    let mut dp = vec![0i32; k + 1];
    for pile in &piles {
      // Build prefix sums for this pile
      let mut prefix = vec![0i32; pile.len() + 1];
      for (i, &c) in pile.iter().enumerate() {
        prefix[i + 1] = prefix[i] + c;
      }
      // Process in reverse to avoid using same pile twice
      for j in (0..=k).rev() {
        for t in 1..=pile.len().min(j) {
          dp[j] = dp[j].max(dp[j - t] + prefix[t]);
        }
      }
    }
    dp[k]
  }
}