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]的最大子序和跟 pb[0]有关,如果pb[0] > 0, pb[1] = pb[0] + nums[1]
    • 如果 pb[0] < 0, 那么 以nums[1]结尾的最大子序就是自己本身(负数+任何数m<任何数m),所以pb[1] = nums[1]
    • 此时得判断下 max和pb[1]谁大, 如果比max大,将值赋值给max
    • 循环到第三个也一样,看pb[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

    }

代码

results matching ""

    No results matching ""