Light's Blog

The best or nothing.

LeetCode Problems 之 分治法

| Comments

分治法

以下为 LeetCode 分治法 相关问题解法记录。

53. 最大子序和

问题分析:求连续子序列最大和。
方法一:模拟。
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        var maxValue = Int.min
        for i in 0..<nums.count {
            var sum = nums[i]
            if maxValue < sum {
                maxValue = sum
            }
            for j in (i+1)..<nums.count {
                sum = sum + nums[j]
                if maxValue < sum {
                    maxValue = sum
                }
            }
        }
        return maxValue
    }
}

方法二:动态规划。
代码:

1
//  待完成

方法三:分治法。

1
//  待完成

启发:连续子序列问题,分治法。

Comments