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

题目要求:

1、输入一个整形数组,数组里有正数也有负数。

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

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

设计思路:

1、建立二维数组Array,第一列存放输入的整数值。第二列存放子数组的和值(限定长度为100,2)

2、定义变量count为输入数字的个数,在循环中输入整数,结束的时候以输入9999代表结束

3、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]

4、最后从Array[][1]此第二列数组中找寻最大值,输出。

import java.util.Scanner;
public class Maxshuzu 
{
    public static void main(String args[])
    {
        int Array[][]=new int[100][2];
        int count=0;
        System.out.println("请输入整数(最多100个),结束请输入9999");
        Scanner shu=new Scanner(System.in);
        
        for(int i=0;i<100;i++)
        {
            Array[i][0]=shu.nextInt();
            if(Array[i][0]==9999)
                {
                    count=i;
                    break;
                }
        }
        Array[0][1]=Array[0][0];
        for(int i=1;i<count;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(int i=1;i<count;i++)
        {
            if(Array[i][1]>Max)
            {
                Max=Array[i][1];
            }
        }
        System.out.println("数组最大值为:"+Max);
    }
}


截图:

存在问题:以9999结尾不够严谨,且没有列出最大数组各项值。(基本功能还是实现了的)

原文地址:https://www.cnblogs.com/maplely/p/5364789.html