LeetCode Ts-2640. Find the Score of All Prefixes of an Array

    AllenLi
    CodingLeetCode Js-PrefixSum

    We define the conversion array conver of an array arr as follows:
    conver[i] = arr[i] + max(arr[0..i]) where max(arr[0..i]) is the maximum value of arr[j] over 0 <= j <= i. We also define the score of an array arr as the sum of the values of the conversion array of arr. Given a 0-indexed integer array nums of length n, return an array ans of length n where ans[i] is the score of the prefix nums[0..I]. 

    我們定義一個轉換陣列 arr ，如下：
conver[i] = arr[i] + max(arr[0..i])
其中 max(arr[0..i])  是 arr[j] 在 0 <= j <= i 範圍內的最大值。
我們也將陣列 arr 的分數定義為 arr 的轉換陣列中所有元素值得總和。
給予一個從 0 開始、長度為 n 的整數陣列 nums，回傳一個長度為 n 的陣列 ans，
其中 ans[i] 是 前綴 nums[0...i] 的分數。

    Example 1:

    Input: nums = [2,3,7,5,10]
Output: [4,10,24,36,56]
Explanation: 
For the prefix [2], the conversion array is [4] hence the score is 4
For the prefix [2, 3], the conversion array is [4, 6] hence the score is 10
For the prefix [2, 3, 7], the conversion array is [4, 6, 14] hence the score is 24
For the prefix [2, 3, 7, 5], the conversion array is [4, 6, 14, 12] hence the score is 36
For the prefix [2, 3, 7, 5, 10], the conversion array is [4, 6, 14, 12, 20] hence the score is 56

    Example 2:

    Input: nums = [1,1,2,4,8,16]
Output: [2,4,8,16,32,64]
Explanation: 
For the prefix [1], the conversion array is [2] hence the score is 2
For the prefix [1, 1], the conversion array is [2, 2] hence the score is 4
For the prefix [1, 1, 2], the conversion array is [2, 2, 4] hence the score is 8
For the prefix [1, 1, 2, 4], the conversion array is [2, 2, 4, 8] hence the score is 16
For the prefix [1, 1, 2, 4, 8], the conversion array is [2, 2, 4, 8, 16] hence the score is 32
For the prefix [1, 1, 2, 4, 8, 16], the conversion array is [2, 2, 4, 8, 16, 32] hence the score is 64

    Solution:
    這題題目希望我們在轉換的陣列中放入當前數值與 0 到當前陣列位置中最大數值的加總，
    所以我們需要定義 ans 陣列來存放數值，
    需要 currentMax 變數來記錄當前最大的數值，
    以及兩者相加的 totalScore。
    接下來就可以進行遍歷 nums 陣列的回圈，
    並做簡單的數學運算即可。

    Code 1: BigO(n)

    function findPrefixScore(nums: number[]): number[] {
    const ans: number[] = [];
    let currentMax: number = 0;
    let totalScore: number = 0;
    for (const num of nums) {
        currentMax = Math.max(num, currentMax);
        const conver: number = num + currentMax;        
        totalScore += conver;
        ans.push(totalScore);
    }
    return ans;
};

    FlowChart:
    Example 1

    Input: nums = [2,3,7,5,10]

num: 2 currentMax: 0
Math.max(num, currentMax): 2
conver: 4
totalScore: 4
ans [ 4 ]

num: 3 currentMax: 2
Math.max(num, currentMax): 3
conver: 6
totalScore: 10
ans [ 4, 10 ]

num: 7 currentMax: 3
Math.max(num, currentMax): 7
conver: 14
totalScore: 24
ans [ 4, 10, 24 ]

num: 5 currentMax: 7
Math.max(num, currentMax): 7
conver: 12
totalScore: 36
ans [ 4, 10, 24, 36 ]

num: 10 currentMax: 7
Math.max(num, currentMax): 10
conver: 20
totalScore: 56
ans [ 4, 10, 24, 36, 56 ]

return ans; // [ 4, 10, 24, 36, 56 ]

    Example 2

    Input: nums = [1,1,2,4,8,16]

num: 1 currentMax: 0
Math.max(num, currentMax): 1
conver: 2
totalScore: 2
ans [ 2 ]

num: 1 currentMax: 1
Math.max(num, currentMax): 1
conver: 2
totalScore: 4
ans [ 2, 4 ]

num: 2 currentMax: 1
Math.max(num, currentMax): 2
conver: 4
totalScore: 8
ans [ 2, 4, 8 ]

num: 4 currentMax: 2
Math.max(num, currentMax): 4
conver: 8
totalScore: 16
ans [ 2, 4, 8, 16 ]

num: 8 currentMax: 4
Math.max(num, currentMax): 8
conver: 16
totalScore: 32
ans [ 2, 4, 8, 16, 32 ]

num: 16 currentMax: 8
Math.max(num, currentMax): 16
conver: 32
totalScore: 64
ans [ 2, 4, 8, 16, 32, 64 ]

return ans; // [ 2, 4, 8, 16, 32, 64 ]

    Related Posts