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


要求: 输入一个整形数组,数组里有正数也有负数。

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

求所有子数组的和的最大值。

要求时间复杂度为O(n)

设计思想:

1、先输入一个数字表示该数组的长度,如果输入的是零或者负数则重新输出。

2、建立二维数组Array[][],一个存储数组元素,一个存储字数组的和。

3、在往数组的第一列中输入整数,数量为之前确定的数组长度,如果输入的是非整数的话跳出程序。

4、首先令Array[0][1]=Array[0][0],然后进入循环判断,从i=1开始,若Array[i-1][1]<=0时,则Array[i][1]=Array[i][0],若Array[i-1][1]>0时,则Array[i][1]=Array[i-1][1]+Array[i][0]

5、最后通过一个for循环从Array[][1]此第二列数组中找出最大值,输出。

源代码:

import java.util.InputMismatchException;
import java.util.Scanner;

public class MaxArray {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int i;
        System.out.println("请输入数组的长度:");
        Scanner sc=new Scanner(System.in);//输入一个数字表示该数组的长度
        int length=sc.nextInt();
        while(length==0||length<0)//如果数组长度为0或者是负数的话重新输入
        {        
            System.out.println("Error!数组长度错误(为零或者负)!请重新输入:");    
            //System.exit(0);
            length=sc.nextInt();
        }
        int Array[][]=new int[100][2];//定义一个二维数组,一个存储数组元素,一个存储字数组和
        System.out.println("请输入一组整数(可正可负):");
        for(i=0;i<length;i++)
        {
            try//如果输入的是非整数的话跳出程序
            {
                 Array[i][0]=sc.nextInt();
            }
            catch(InputMismatchException e)
            {
                System.out.println("Error!");
                break;
            }         
        }
        Array[0][1]=Array[0][0];
        for(i=1;i<length;i++)
        {
            if(Array[i-1][1]<=0)
            {
                Array[i][1]=Array[i][0];
            }
            if(Array[i-1][1]>0)
            {
                Array[i][1]=Array[i-1][1]+Array[i][0];
            }
        }
        int Max=Array[0][1];
        for(i=1;i<length;i++)
        {
            if(Array[i][1]>Max)
            {
                Max=Array[i][1];
            }
        }
        System.out.println("该数组中子数组中的最大值为:"+Max);
    }
}

结果截图:

总结:主要是利用创立一个二维数组来分别存储数组数据和字数组和的数据,然后来通过比较给出字数组中的最大值。

优质内容筛选与推荐>>
1、python递归
2、JavaScript中的this关键字的用法和注意点
3、Linux企业级项目实践之网络爬虫(11)——处理http请求头
4、第三章 Git的入门 - 读书笔记
5、获得超类的泛型参数在子类实例化传入的实际类型


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号