给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
动态规划：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| object MaxSubSeqSum {
def main(args: Array[String]): Unit = {
println(maxSubArray(Array(-2, 1, -3, 4, -1, 2, 1, -5, 4)))
println(maxSubArray(Array(-1, -2)))
}
def maxSubArray(nums: Array[Int]): Int = {
if (nums.length == 0) return 0
if (nums.length == 1) return nums(0)
val dp = new Array[Int](nums.length)
dp(0) = nums(0)
var max = dp(0)
for (i <- 1 until nums.length) {
if (dp(i - 1) >= 0) {
dp(i) = dp(i - 1) + nums(i)
} else {
dp(i) = nums(i)
}
if (dp(i) > max) {
max = dp(i)
}
}
max
}
}
|