景德镇市网站建设_网站建设公司_Banner设计_seo优化

题目链接：3788. 分割的最大得分（中等）

算法原理：

解法：前缀和+模拟

7ms击败44.17%

时间复杂度O(N)

思路很简单，用prefix数组记录前缀和，用suffix记录该数之后的最小值，一次遍历取差的最大值作为返回值即可

Java代码：

class Solution { public long maximumScore(int[] nums) { int n=nums.length; long[] prefix=new long[n]; prefix[0]=nums[0]; long[] suffix=new long[n]; suffix[n-1]=nums[n-1]; long ret=Long.MIN_VALUE; for(int i=1;i<n;i++) prefix[i]=prefix[i-1]+nums[i]; for(int i=n-2;i>=0;i--) suffix[i]=Math.min(suffix[i+1],nums[i]); for(int i=0;i<n-1;i++) ret=Math.max(ret,prefix[i]-suffix[i+1]); return ret; } }