返回一个整数数组中最大子数组的和。

 

要求：

　　输入一个整形数组，数组里有正数也有负数。

　　数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

　　求所有子数组的和的最大值。要求时间复杂度为O(n)

　　发表一篇博客文章讲述设计思想，出现的问题，可能的解决方案（多选）、源代码、结果截图、总结。

 

一开始的代码只实现了功能，并没有达到要求的时间复杂度为O（n），设计思想为：先定义sum赋值数组中的最大值，然后开始遍历，先从第一个数开始加比如：1,2,3,4,5,6,7,8,9,10     先从1开始加，1+2然后赋值给sum1，再给sum比较，把较大者赋值给sum，然后1+2+3重复以上步骤，等到1加完后，再从2开始重复以上步骤直到结束。

代码为：

import java.util.Scanner;

public class Shuzu{
    public static void main(String[] args){
            Scanner sc=new Scanner(System.in);
            System.out.println("输入10个数");
            int num[]=new int[10];
            int sum=0;
            int sum1=0;
            for(int i=0;i<10;i++) {
                num[i]=sc.nextInt();
                if(num[i]>sum) {
                    sum=num[i];
                }
            }
            for(int i=0;i<10;i++) {
                sum1=num[i];
                for(int j=i+1;j<10;j++) {
                    sum1=sum1+num[j];
                    if(sum1>sum) {
                        sum=sum1;
                    }
                }
            }
            System.out.println("最大和为："+sum);
       }
}

方法二：把数组的第一个值付给rmax和max，随后进行循环比较，从正值开始计数，如果一个一个累加起来小于等于零，就将max重新赋值，每次把最大值付给rmax，最后得出子数组的和的最大值。

package about_bank_account;

import java.util.Scanner;

public class Test {
    
    public static void main (String[] args){
        @SuppressWarnings("resource")
        Scanner in=new Scanner(System.in);
        int num[]=new int[5];
        int max=0;
        int rmax=0;
        System.out.println("请输入五个数：");
        for(int i=0;i<5;i++) {
            num[i]=in.nextInt();
        }
        rmax=num[0];
        for(int i=0;i<5;i++) {
            if(max<=0) {
                max=num[i];
            }else {
                max+=num[i];
            }
            if(rmax<max) {
                rmax=max;
            }
        }
        System.out.println(rmax);     
    }
    
}