环形数组求最大子数组
题目:
返回一个整数数组中最大子数组的和。
要求:
输入一个整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
如果数组A[0]……A[j-1]首尾相邻,允许A[i-1], …… A[n-1], A[0]……A[j-1]之和最大。
同时返回最大子数组的位置。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
解决思路:
1.用随机函数产生含有N个元素的一维数组
2.构造长度为2N的数组,前N个依次元素是随机函数产生的一维数组中的元素,后N个元素也是随机函数产生的一维数组中的元素。
3.按照求取一维数组中最大子数组的方法求取长度为2N的一维数组的最大子数组。
4.在求长度为2N的一维数组的最大子数组的过程中对求出的子数组中的元素进行判断,看是否子数组中的元素已经发生重复,若未重复则继续进行,否则,退出,得到最大子数组。
源代码:
import java.util.Random;
import java.util.Scanner;
public class zuidashuzu_xunhuan{
/**
* @param args
*/
public static void main(String[] args) {
// TODO 自动生成的方法存根
int array[]=new int[100];
int flag_qi=0;
int flag_zh=0;
int flag1=0;
int flag2=0;//分别记录子数列的起始和结束位置
int sum,sumtemp;//表示子数列的和
Random r=new Random();
System.out.print("请输入数组元素的个数: ");
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
System.out.println("--------------------------------" +
"------------------------------------------");
for(int i=0;i<a;i++){
array[i]=r.nextInt()%10;
array[a+i]=array[i];
}
System.out.print("产生的随机数序列为: ");
for(int i=0;i<a;i++){
System.out.print(array[i]+" ");
}
System.out.println("");
sum=array[0];
sumtemp=sum;
for(int i=0;i<2*a;i++){
if(sumtemp<=0){
sumtemp=0;
flag_qi=i+1;
flag_zh=i;
}
if(i+1!=flag_qi+a){
sumtemp+=array[i+1];
flag_zh++;
if(sumtemp>sum){
sum=sumtemp;
flag1=flag_qi;
flag2=flag_zh;
}
}
else
break;
}
System.out.print("子数组的组成元素为: ");
for(int i=flag1;i<=flag2;i++)
System.out.print(array[i]+" ");
System.out.println('\n'+"子数组和的最大值为: "+sum);
}
}
截图:
遇到的困难:
初见题目时对题目理解不到位,在想到将首尾相连的长度为N的一维数组转化为长度为2N的普通的一维数组的方法后,错误的以为最大子数组的长度可以大于N,故使后续处理特殊情况的方法发生变化,错误的理解了题意。后来和同伴的交流中发现自己的错误并改正。
总结:
学会将自己不熟悉的模型转化为熟悉的模型,解决问题是一种方法与能力。
相关文章
- arraylist扩容是创建新数组吗 java_arraylist扩容机制要怎么实现?arraylist怎么扩容…「建议收藏」
- 2022-09-07:给你一个由正整数组成的数组 nums 。 数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。 例如,序列 [4,6,16
- java 输入数组,最大的与第一个元素交换,最小的与最后一个元素交换,输出数组
- 【说站】php中PDO获取关联数组
- 215. 数组中的第K个最大元素
- 连续子数组的最大和
- js数组删除指定元素splice_js找出数组中最大的数
- 2022-12-06:定义一个概念叫“变序最大和“ “变序最大和“是说一个数组中,每个值都可以减小或者不变, 在必须把整体变成严
- 数组中两元素的最大乘积 : 简单模拟题
- 【力扣/牛客刷题】136. 只出现一次的数字 || 75. 颜色分类 || 215. 数组中的第K个最大元素
- Numpy ndarray多维数组
- Oracle中有效运用数组的方法(oracle中使用数组)
- PHParray_flip()删除重复数组元素专用函数
- php数组函数序列之next()-移动数组内部指针到下一个元素的位置,并返回该元素值
- 求子数组最大和的解决方法详解
- jQuery教程$()包装函数来实现数组元素分页效果
- 求数组最大最小值方法适用于任何数组
- C#的锯齿数组以及C++实现代码
- Js获取数组最大和最小值示例代码
- 理解Golang中的数组(array)、切片(slice)和map
- Ruby字符串、条件、循环、数组、Hash、类基本操作笔记