题解 | #连续子数组的最大和(二)#
连续子数组的最大和(二)
https://www.nowcoder.com/practice/11662ff51a714bbd8de809a89c481e21
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
export function FindGreatestSumOfSubArray(array: number[]): number[] {
// write code here
const cache: number[] = new Array(array.length)
cache[0] = array[0]
let max = cache[0]
let resLeft = 0
let resRight = 0
let left = 0
let right = 0
for (let i = 1; i < array.length; i++) {
right = i
const currentMax = cache[i - 1] + array[i]
cache[i] = Math.max(currentMax, array[i])
if (currentMax < array[i]) {
left = i
}
if (max <= cache[i]) {
resLeft = left
resRight = right
max = cache[i]
}
}
return array.slice(resLeft, resRight + 1)
}
