Ex-Amazon explains solution with a video, Python, JavaScript, Java and C++
My youtube channel - KeetCode(Ex-Amazon)\nI create 154 videos for leetcode questions as of April 21, 2023. I believe my channel helps you prepare for the coming
# My youtube channel - KeetCode(Ex-Amazon)\nI create 154 videos for leetcode questions as of April 21, 2023. I believe my channel helps you prepare for the coming technical interviews. Please subscribe my channel!\n\n### Please subscribe my channel - KeetCode(Ex-Amazon) from here.\n\n**I created a video for this question. I believe you can understand easily with visualization.** \n\n**My youtube channel - KeetCode(Ex-Amazon)**\nLink from LeetCode profile\nhttps://leetcode.com/niits/\n\n![FotoJet (51).jpg](https://assets.leetcode.com/users/images/cfe17a12-e27b-4d31-bd0f-b52d0a597c5c_1681608709.804891.jpeg)\n\n\n---\n\n\n\n# Intuition\nApply Dynamic Programming to this question.\n\n# Approach\n1. Initialize an array prev with k + 1 elements, all set to 0.\n\n2. Iterate over each pile in piles:\n\n  - Initialize an array sum_list with a single element 0, representing the prefix sum of coins in the pile.\n  - Initialize a variable total to 0, to keep track of the total sum of coins in the pile.\n  - Iterate over each coin in the pile:\nAdd the coin to total.\nAppend total to sum_list, representing the cumulative sum of coins in the pile.\n\n3. Initialize an array cur_max with k + 1 elements, all set to 0, to keep track of the maximum value for each number of coins picked.\n\n4. Iterate over each number of coins n from 1 to k:\n\n  - Calculate the range of elements to consider in sum_list as calc_range, which is the minimum of n + 1 and the length of sum_list.\n  - For each position pos in the range of calc_range:\n    - Update cur_max[n] with the maximum value between its current value and the sum of sum_list[pos] and prev[n - pos], which represents the maximum value achievable by picking n coins from the current pile.\n\n5. Update prev with the values of cur_max, representing the maximum value achievable by picking n coins from all previous piles.\n\n6. After iterating over all piles, the final result will be stored in prev[k], which represents the maximum value achievable by picking k coins from all piles.\n\n7. Return prev[k] as the result of the function.\n\n# Complexity\n- Time complexity: O(NK)\nN is the length of the piles list (number of piles) and K is the input integer k. This is because the code iterates over each pile and for each pile, it performs calculations up to k iterations.\n\n- Space complexity: O(K)\nThe code uses two lists (prev and cur_max) of length k + 1 to store intermediate results for each value of k. The sum_list list also has a maximum length of k + 1 for each pile. Therefore, the total space complexity is dominated by the prev and cur_max lists, which have a space complexity of O(K).\n\n# Python\n```\nclass Solution:\n    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n\n        prev = [0] * (k + 1)\n\n        for pile in piles:\n            sum_list = [0]\n            total = 0\n            for coin in pile:\n                total += coin\n                sum_list.append(total)\n        \n            cur_max = [0] * (k + 1)\n\n            for n in range(1, k + 1):\n                calc_range = min(n + 1, len(sum_list))\n                cur_max[n] = max(sum_list[pos] + prev[n - pos] for pos in range(calc_range))\n            \n            prev = cur_max\n        \n        return prev[k]\n```\n# JavaScript\n```\n/**\n * @param {number[][]} piles\n * @param {number} k\n * @return {number}\n */\nvar maxValueOfCoins = function(piles, k) {\n    let prev = new Array(k + 1).fill(0);\n\n    for (let pile of piles) {\n        let sumList = [0];\n        let total = 0;\n        for (let coin of pile) {\n            total += coin;\n            sumList.push(total);\n        }\n\n        let curMax = new Array(k + 1).fill(0);\n\n        for (let n = 1; n <= k; n++) {\n            let calcRange = Math.min(n + 1, sumList.length);\n            for (let pos = 0; pos < calcRange; pos++) {\n                curMax[n] = Math.max(curMax[n], sumList[pos] + prev[n - pos]);\n            }\n        }\n\n        prev = curMax;\n    }\n\n    return prev[k];\n};\n```\n# Java\n```\nclass Solution {\n    public int maxValueOfCoins(List<List<Integer>> piles, int k) {\n        int[] prev = new int[k + 1];\n\n        for (List<Integer> pile : piles) {\n            List<Integer> sumList = new ArrayList<>();\n            sumList.add(0);\n            int total = 0;\n            for (int coin : pile) {\n                total += coin;\n                sumList.add(total);\n            }\n\n            int[] curMax = new int[k + 1];\n\n            for (int n = 1; n <= k; n++) {\n                int calcRange = Math.min(n + 1, sumList.size());\n                for (int pos = 0; pos < calcRange; pos++) {\n                    curMax[n] = Math.max(curMax[n], sumList.get(pos) + prev[n - pos]);\n                }\n            }\n\n            prev = curMax;\n        }\n\n        return prev[k];        \n    }\n}\n```\n# C++\n```\nclass Solution {\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        std::vector<int> prev(k + 1, 0);\n\n        for (const auto& pile : piles) {\n            std::vector<int> sumList(1, 0);\n            int total = 0;\n            for (int coin : pile) {\n                total += coin;\n                sumList.push_back(total);\n            }\n\n            std::vector<int> curMax(k + 1, 0);\n\n            for (int n = 1; n <= k; n++) {\n                int calcRange = std::min(n + 1, static_cast<int>(sumList.size()));\n                for (int pos = 0; pos < calcRange; pos++) {\n                    curMax[n] = std::max(curMax[n], sumList[pos] + prev[n - pos]);\n                }\n            }\n\n            prev = curMax;\n        }\n\n        return prev[k];        \n    }\n};\n```
['C++', 'Java', 'Python3', 'JavaScript']