最大子数组下标java_返回一个整数数组中最大子数组的和——java程序设计

一、题目要求

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

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

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

二、设计思想

解决方案一：

1、通过用户输入数组容量，随机产生一个整型数组

2、将数组元素依次相加进行判断，当遇到小于0的数时停止相加(因为要求最大子数组的和，加上小于0的数会让子数组和变小)

3、遍历相加的过程中不断更新子数组的和sum以及最大值max的值

4、遍历完成后输出max值即可

解决方案二：

1、通过用户输入数组容量，随机产生一个整型数组

2、通过循环遍历所有元素求出以该元素为首节点的所有子数组的和，将其存入一个list中

3、求出list的最大值

三、源代码

由于解决方案二的复杂度高于解决方案一，这里只给出解决方案一的代码

public static int getResult(ArrayList array) {

int sum = 0;

int result = array.get(0);

for (Integer integer : array) {

if(sum<=0)

sum = integer;

else

sum += integer;

if(sum>result)

result = sum;

}

return result;

}

四、扩展

若将原数组首尾相连改为环状数组，求其最大子数组的和解决方案如下：

1、通过用户输入数组容量，随机产生一个整型数组

2、遍历数组中的所有元素，保证让其每个元素都作为一次首节点，将其前面的元素拼到原数组最后使其成为一个新数组

3、对每个新数组求一次最大子数组

4、将所有最大子数组的值比较大小，输出最大值

源代码如下：

import java.util.ArrayList;

import java.util.Scanner;

public class FirstTest {

public static int getResult(ArrayList array) {

int sum = 0;

int result = array.get(0);

for (Integer integer : array) {

if(sum<=0)

sum = integer;

else

sum += integer;

if(sum>result)

result = sum;

}

return result;

}

public static void main(String[] args) {

Scanner input=new Scanner(System.in);

int num=input.nextInt();

int array[]=new int[num];

ArrayList result = new ArrayList<>();

for(int i=0;i

{

if((int)(Math.random()*2)==0)

{

array[i]=(int)(Math.random()*10);

}

else

{

array[i]=-(int)(Math.random()*10);

}

}

for(int i=0;i

System.out.println(array[i]);

}

for(int i=0;i

ArrayList list = new ArrayList<>();

for(int j=i;j

list.add(array[j]);

}

for(int k=0;k

list.add(array[k]);

}

result.add(getResult(list));

}

int max = result.get(0);

for (Integer integer : result) {

if(max

max = integer;

}

System.out.println(max);

}

}

运行结果截图：

  

软件工程结对开发——返回一个整数数组中最大子数组的和(JAVA)

题目:返回一个整数数组中最大子数组的和. 要求: 输入一个整型数组,数组里有正数也有负数: 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和: 求所有子数组的和的最大值.要求时间复杂度为 ...

求一个数组的最大子数组(C/C++实现)

最大子数组:要求相连,加起来的和最大的子数组就是一个数组的最大子数组.编译环境:VS2012,顺便说句其实我是C#程序员,我只是喜欢学C++. 其实这是个半成品,还有些BUG在里面,不过总体的思路是这 ...

Task 4.3 求环形数组的最大子数组和

任务要求:输入一个整形数组,数组里有正数也有负数. 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和.    如果数组A[0]……A[j-1]首尾相邻,允许A[i-1], …… A[n- ...

求解数组环中最大子数组和的问题(java)

//石家庄铁道大学 信1405-1 班 唐炳辉 在上一次作业中,对于普通数组的最大子数组的求解问题的基础上,将普通的数组变成一个首尾相接的环,求这个环的最大子数组.类似的,只要改变普通数组的数组位置, ...

[Jobdu] 题目1527：首尾相连数组的最大子数组和

题目描述: 给定一个由N个整数元素组成的数组arr,数组中有正数也有负数,这个数组不是一般的数组,其首尾是相连的.数组中一个或多个连续元素可以组成一个子数组,其中存在这样的子数组arr[i],…arr ...

蚂蚁的难题(二)首尾相连数组的最大子数组和(DP)

蚂蚁的难题(二) 时间限制:1000 ms  |  内存限制:65535 KB 难度:3 描述 下雨了,下雨了,蚂蚁搬家了. 已知有n种食材需要搬走,这些食材从1到n依次排成了一个圈.小蚂蚁对每种食材 ...

随机推荐

java 线程池——异步任务

一.简单粗暴的线程 最原始的方式,当我们要并行的或者异步的执行一个任务的时候,我们会直接使用启动一个线程的方式,如下面所示: new Thread(new Runnable() { @Override ...

c++ 一些随笔

1. A region of source code where any use of the unqualified name (that is, as a plain identifier) re ...

PHP 页面跳转方法

1.php header()函数跳转 PHP的header()函数非常强大,其中在页面url跳转方面也调用简单,使用header()直接跳转到指定url页面,这时页面跳转是302重定向: $url = ...

JS 用window.open()函数，父级页面如何取到子级页面的返回值？

父窗口:

初识MFC,WinForm,WPF，Q&#39;t

MFC和QT是C++中常见的GUI框架,而WinForm和WPF是C#中常用的框架,不过我们一般很少叫WinForm框架,可能直接叫图形控件类库更多点.反正只是个称呼罢了,爱咋叫就咋叫.另外WinFo ...

ios引导页 设定以及 图片尺寸

iphone的屏幕尺寸有着几种: iphone 4/4s: 3.5 寸 分辨率:640X960 高宽比 640/960 = 1.5 iphone 5/5c/5s:4 寸 分辨率:640X1136  ...

angular的那些事

angular.js是什么 AngularJS 是一个 JavaScript 框架.它可通过

机器学习基石：13 Hazard of Overfitting

泛化能力差和过拟合: 引起过拟合的原因: 1)过度VC维(模型复杂度高)------确定性噪声: 2)随机噪声: 3)有限的样本数量N. 具体实验来看模型复杂度Qf/确定性噪声.随机噪声sigma2. ...

Lesson 2-4(字典)

2.7 字典 &.字典是许多值的集合,索引可以使用许多不同的数据类型,不只是整数,可以是数.字符串或元组. &.字典的索引被称为“键”,键及其关联的值称为“键-值”对,这种键-值对也称 ...

csharp: Configuring ASP.NET with Spring.NET and FluentNHibernate

Domain: FluentNhibernateLocalSessionFactoryObject.cs using System; using System.Collections.Generic; ...