剑指Offer:连续子数组的最大和

女爷i 2022-04-25 04:40 192阅读 0赞

题目：  
输入一个整型数组,数组里有正也有负，数组中的一个或者多个连续整数，组成一个子数组，求所有子数组的和的最大值。输入1，-2,3,10，-4,7,2，-5。

提一下，当没有思路的时候，**从画图，举例子，分解问题入手**  
思路一：  
当遍历第一个数，加入sum,如果sum<=0，即sum+=nums\[i\]，如果sum>0，即连续的sum+=num\[i+1\]，那么还有一种情况就是，在连续的正数过程中，可能出现一个负数，会使当前sum减少。那么设置MAXSum.在每次比较后都进行判断。把每次的最大正数保存下来。这样不断往下。那么都会把最大的子数组的数给存下来。

代码： **不过下面的2个代码我都只是没有考虑非法输入问题等情况。**

public int MaxSub(int[] nums,int length){
    
            int sum = 0;
    
            int MaxSum = 0;
    
            for(int i=0;i<length;i++){
    
                if(sum<=0){
    
                    sum = nums[i];
                }else{
    
                    sum+= nums[i];
                }
    
                if(MaxSum<sum){
    
                    MaxSum = sum;
                }
    
            }
    
            return MaxSum;
    
        }
    
    
        public static void main(String[] args) {
    
            int[] nums = {1,-2,3,10,-4,7,2,-5};
            System.out.println(new MaxSub().MaxSub(nums,nums.length));
    
        }

思路二:**动态规划**  
设置f(i)为当前到i为止最大的子数组和。  
那么得到了一个递推公式  
![在这里插入图片描述][20190501121335538.png]  
这里要说一下。我之前遇到过有的动态规划。  
即再f(i)时，把当前n(i)算进去和不算进去的情况.

{  f(i-1)+n(i);
    即f(i)={
    		{  f(i-1)

即这样的思维，但是也有一种，就上面这个题目的情况，当前的n(i)都算上，但是不算前面的f(i-1).这样的情况

代码：

//动态规划
        public int MaxSubs(int[] nums,int lengths){
    
            int[] sums = new int[lengths];
    
    
            sums[0] = nums[0];
    
            for(int i=1;i<lengths;i++){
    
                sums[i] = Math.max(nums[i],nums[i]+sums[i-1]);
    
            }
    
            Arrays.sort(sums);
    
            return sums[lengths-1];
        }
    
    
        public static void main(String[] args) {
    
            int[] nums = {1,-2,3,10,-4,7,2,-5};
            System.out.println(new MaxSub().MaxSubs(nums,nums.length));
    
        }

建议：leetcode 第三题可以做做，用的是滑动窗口方法。

[20190501121335538.png]: /images/20220210/e7e42eff7f6e42bd9831403cf1f35668.png