1.1. 题目
1.1.1. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
1.1.2. 题解:
- 数组里连续位置的元素之和,得最大的和
- 数组本身也是自己的子数组
- 必须是连续的,不能跳跃
1.1.3. 思路:
第一反应,暴力解决
- 先从第一个元素开始,定义一个最大值max,定义一个临时值
- 第一个元素为最大,然后加上第二个值,比谁大,谁大就赋值给max
- 再加上第三个值,与当前的 max比谁大,谁大谁赋值给max
- 待数组第一次全部加完,就从数组第二个值开始再来一遍,一直到所有数组值作为开头都遍历过!
- 求的最大值
其实知道这题可以 动态规划来解,只是我还不是很会..所以参考了其他人的写法
- 动态规划一般是假设当前是结尾来往前算..
- 定义一个最大值max,定义一个以当前节点为尾节点的最大子序dp切片
- 用上面的例子来看
[-2,1,-3,4,-1,2,1,-5,4] - 比如第一个元素,另max=nums[1],dp[1]肯定等于-2
- 当循环到第二个元素
1的时候, 以1结尾的子序和有1,1+前面最大的子序也就是dp[0]的子序和的值 - 为什么这么说,你想想,你和你前面的数的最大值 是不是等于 你 + 你前面最大值的的和, 我们已知前面一个最大的和是 dp[0]
- 如果 dp[1] 是 以当前值为结尾的最大子序和, 那么dp[1] 要么就是 nums[1] + dp[0] 的和,要么就是 nums[1]本身
- 为什么这么说,因为必须以nums[1]自己本身结尾,如果 dp[0]>=0, 正数+任何数 肯定是大于自己本身的, 如果dp[0] < 0,负数+任何数肯定是小于这个数本身的
- 所以nums[1]的最大子序和跟 dp[0]有关,dp[0] > 0, dp[1] = dp[0] + nums[1]
- 如果 dp[0] < 0, 那么 以nums[1]结尾的最大子序就是自己本身(负数+任何数m<任何数m),所以pb[1] = nums[1]
- 此时得判断下 max和dp[1]谁大, 如果比max大,将值赋值给max
- 循环到第三个也一样,看dp[1]是大于零还是小于零
- 其实很难想的.. 可能是还不熟练....
1.1.4. 代码:
点击显示
// 动态规划
func maxSubArray2(nums []int) int {
maxLen := len(nums)
// 如果数组就一位,直接返回值
if maxLen == 1 {
return nums[0]
}
var max int
pb := make([]int,maxLen)
pb[0] = nums[0]
max = pb[0]
for i:=1;i<maxLen;i++ {
if nums[i] + pb[i-1] >= nums[i] {
// 等同于 if pb[i-1] >= 0 {
pb[i] = nums[i] + pb[i-1]
} else {
pb[i] = nums[i]
}
if pb[i] > max {
max = pb[i]
}
}
return max
}
// 暴力解决
func maxSubArray(nums []int) int {
// 获取数组长度
maxLen := len(nums)
// 如果数组就一位,直接返回值
if maxLen == 1 {
return nums[0]
}
var max int
for i:=0;i<maxLen;i++ {
var temp int
for j:=i;j<maxLen;j++ {
// 每次的和
temp = temp + nums[j]
// 如果是第一个值的第一次循环 此时max为0,但temp第一个值可能为负数,所以把第一个值赋值给max
if i == 0 && j == 0 {
max = temp
}
// 每当有大的值,就赋值给max
if temp > max {
max = temp
}
}
}
return max
}