36 lines
1.1 KiB
JavaScript
36 lines
1.1 KiB
JavaScript
/**
|
|
* @param {number[]} nums
|
|
* @return {number}
|
|
*/
|
|
const maxSubarraySumCircular = function (nums) {
|
|
|
|
};
|
|
|
|
/*
|
|
最大子数组之和无外乎两种情况，子数组在开头和结尾直接，还有一种情况就是一部分在开头的前缀，一部分在结尾的后缀，
|
|
所以只需一次遍历统计前缀和的最大值和第一种情况的最大值，之后再倒序遍历统计后缀的最大值，之后比较这两种情况
|
|
*/
|
|
function f1(nums) {
|
|
const n = nums.length;
|
|
const leftMax = new Array(n).fill(0);
|
|
// 对坐标为 0 处的元素单独处理，避免考虑子数组为空的情况
|
|
leftMax[0] = nums[0];
|
|
let leftSum = nums[0];
|
|
let pre = nums[0];
|
|
let res = nums[0];
|
|
for (let i = 1; i < n; i++) {
|
|
pre = Math.max(pre + nums[i], nums[i]);
|
|
res = Math.max(res, pre);
|
|
leftSum += nums[i];
|
|
leftMax[i] = Math.max(leftMax[i - 1], leftSum);
|
|
}
|
|
|
|
// 从右到左枚举后缀，固定后缀，选择最大前缀
|
|
let rightSum = 0;
|
|
for (let i = n - 1; i > 0; i--) {
|
|
rightSum += nums[i];
|
|
res = Math.max(res, rightSum + leftMax[i - 1]);
|
|
}
|
|
return res;
|
|
}
|