6334. 一个数组所有前缀的分数 - Java 前缀和

原题地址：https://leetcode.cn/problems/find-the-score-of-all-prefixes-of-an-array/

题解

题目要求返回一个数组，其实我们直接看最后两段：ans[i]是nums[0]——nums[i]的conver之和

也可以写成：ans[i]=ans[i-1]+conver[i]

那么实际上conver[i]只有在遍历到i的时候才会用到，也就没有必要开一个数组了，直接在遍历到i的时候计算i的conver即可

每次遍历分三步：

• 用一个max维护nums[0]——nums[i]的最大值
• conver=max+nums[i]
• ans[i]=ans[i-1]+conver

实际上如果进一步简化的话，可以直接写成ans[i]=ans[i-1]+max+nums[i]

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    public long[] findPrefixScore(int[] nums) {
        long[] ans=new long[nums.length];
        int max=0,conver;
        
        for(int i=0;i<nums.length;i++){
            if(max<nums[i])max=nums[i];

            conver=max+nums[i];

            if(i==0)ans[i]=conver;
            else ans[i]=ans[i-1]+conver;
        }
        return ans;
    }
}