两种方法, 分别为 o(n3) 和 o(n)
第一种采用简单的多次遍历, 比较, 使用了三层 for 循环, 复杂度比较高, 为初步构思的结果.
第二种采用直接一次遍历, 第一个正数和出现后, 使用 max 变量进行存储, 继续进行遍历, 将每次获得的 sum 都和 max 进行比较, 将 max 置为最大值, 如果 sum 小于 max 则不改变, 并继续遍历, 如果 sum 出现小于 0, 则将 sum 置为 0, 继续进行遍历, 循环直到数组结束. 进行了初步验证代码应该正确.
- package shuzu;
- import java.util.Scanner;
- public class Shuzu {
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- int[] a = new int[5];
- // 控制台输入数组值
- for (int i = 0; i <a.length; i++) {
- System.out.println("请输入第" + (i + 1) + "个数字:");
- int num = sc.nextInt();
- a[i] = num;
- }
- int max=a[0];
- sc.close();
- for(int j=0;j<a.length;j++) {
- for(int k=0;k<a.length;k++) {
- int sum= 0;
- for(int l=0;l<a.length;l++) {
- sum+=a[l];
- }
- if(sum>max) max=sum;
- }
- }
- System.out.println(max);
- return;
- }
- }
- o(n3)
- package shuzu;
- import java.util.Scanner;
- public class shuzu2 {
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- Scanner sc = new Scanner(System.in);
- int[] a = new int[20];
- // 控制台输入数组值
- for (int i = 0; i <a.length; i++) {
- System.out.println("请输入第" + (i + 1) + "个数字:");
- int num = sc.nextInt();
- a[i] = num;
- }
- sc.close();
- int max=a[0];
- int sum=a[0];
- for(int i=1;i<a.length;i++) {
- if(sum<0)
- sum=a[i];
- else
- sum+=a[i];
- if(sum>max) max=sum;
- }
- System.out.println(max);
- }
- }
来源: http://www.bubuko.com/infodetail-2989591.html