arrays - 查找数组中开始/结束索引的所有可能排列

Question

我正在尝试编写一个方法，该方法返回 Swift 中 subArray 的元素可以获得的最大值。

我遇到的问题是创建一个算法，该算法捕获通过 sliceSum 方法运行的 ArraySlice 的开始和结束索引的所有可能排列。

我知道解决方案很简单，但我想不出。我欢迎关于如何通过 sliceSum 方法实现运行所有可能排列的目标的建议。

func maxSubArray(_ nums: [Int]) -> Int {
    var output = 0

    func sliceSum(slice: ArraySlice<Int>) -> Int {
        // throws out cases that don't work
        guard slice.count > 0 || slice.count != nums.count else { return 0 }
        return slice.reduce(0, +)
    }

    var begin = 0
    var end = nums.count - 1

    while begin < end {
        let frontSlice = nums[begin...end]
        if sliceSum(slice: frontSlice) > output {
            output = sliceSum(slice: frontSlice)
        }

        begin += 1
        end -= 1
    }

    return output
}

鉴于以下情况，我应该返回 6，这是以下数组中切片 [4,-1,2,1] 的总和:

let array = [-2,1,-3,4,-1,2,1,-5,4]
maxSubArray(array)

感谢阅读。我欢迎您提出建议。

Answer 1

如果我理解您的目标，您需要两个循环。将 while 循环和 begin 和 end 变量替换为:

for begin in 0..<nums.count {
    for end in begin..<nums.count {
        let frontSlice = nums[begin...end]
        let sum = sliceSum(slice: frontSlice)
        if sum > output {
            output = sum
        }
    }
}

我还会将您的 sliceSum 重做为:

func sliceSum(slice: ArraySlice<Int>) -> Int {
    if slice.count > 0 {
        return slice.reduce(0, +)
    } else {
        return 0
    }
}