连续子序列求和的最大值

标签: 面试

输入一个整数序列(浮点数序列也适合本处讲的算法),求出其中连续子序列求和的最大值。
在这里插入图片描述
在这里插入图片描述

public static int maxLength(int []arr,int k)
	{
		if(arr==null||arr.length==0)
		{
			return 0;
		}
		HashMap<Integer,Integer>map=new HashMap<Integer,Integer>();
		map.put(0, -1);
		int len=0;
		int sum=0;
		for(int i=0;i<arr.length;i++)
		{
			sum+=arr[i];
			if(map.containsKey(sum-k)) {
				len=Math.max(i-map.get(sum-k), len);
			}
			if(!map.containsKey(sum)) {
				map.put(sum, i);
			}
		}
		return len;
	}

在这里插入图片描述
在这里插入图片描述

public static int mostEOR(int []arr)
	{
		int ans=0;
		int xor=0;
		int []mosts=new int [arr.length];
		HashMap<Integer,Integer>map=new HashMap<>();
		map.put(0, -1);
		for(int i=0;i<arr.length;i++)
		{
			xor^=arr[i];//异或和
			if(map.containsKey(xor)) {
				int pre=map.get(xor);
				//出现异或和为0的位置,这是属于第二种情况
				//pre==-1表明没有数字,只有1个异或和0的数组
				mosts[i]=pre==-1?1:(mosts[pre]+1);
			}
			if(i>0) {
				//第一种情况,最后一块异或和不为0
				mosts[i]=Math.max(mosts[i-1], mosts[i]);
			}
			map.put(xor, i);
			ans=Math.max(ans, mosts[i]);
		}
		return ans;
	}
版权声明:本文为wysw1998原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/wysw1998/article/details/98107870

智能推荐

Qt 之 Query Model Example 解析

总体概括 Query Model Example主要演示了怎么使用QSqlQueryModel这个数据库查询模型类。其中包括创建普通的数据库查询模型、可编辑的数据库查询模型和自定义的数据库查询模型。普通(默认)的数据库查询模型是只读的(不可再模型中编辑数据,模型只通过视图展示数据);可编辑的数据库查询模型重写了QSqlQueryModel的flags()方法和setData()方法;自定义的数据库...

Flutter:Scaffold.of() called with a context that does not contain a Scaffold.

Flutter:Scaffold.of() called with a context that does not contain a Scaffold. 当我第一次点击按钮想要弹出底部消息时出现了如下错误 当BuildContext在Scaffold之前时,调用Scaffold.of(context)会报错。这时可以通过Builder Widget来解决,代码如下:...

【机器学习基础】线性回归

                                                        &nbs...

08-Vue实现书籍购物车案例

书籍购物车案例 index.html main.js style.css 1.内容讲解 写一个table和thead,tbody中每一个tr都用来遍历data变量中的books列表。 结果如下: 在thead中加上购买数量和操作,并在对应的tbody中加入对应的按钮。结果如下: 为每个+和-按钮添加事件,将index作为参数传入,并判断当数量为1时,按钮-不可点击。 结果如下: 为每个移除按钮添加...

堆排序

堆排序就是利用堆进行排序的方法,基本思想是,将代排序列构造成一个大根堆,此时整个序列的最大值就是堆顶的根节点。将它与堆数组的末尾元素交换,此时末尾元素就是最大值,移除末尾元素,然后将剩余n-1个元素重新构造成一个大根堆,堆顶元素为次大元素,再次与末尾元素交换,再移除,如此反复进行,便得到一个有序序列。 (大根堆为每一个父节点都大于两个子节点的堆) 上面思想的实现还要解决两个问题: 1.如何由一个无...

猜你喜欢

基础知识(变量类型和计算)

一、值类型 常见的有:number、string、Boolean、undefined、Symbol 二、引用类型 常用的有:object、Array、null(指针指向为空)、function 两者的区别: 值类型暂用空间小,所以存放在栈中,赋值时互不干扰,所以b还是100 引用类型暂用空间大,所以存放在堆中,赋值的时候b是引用了和a一样的内存地址,所以a改变了b也跟着改变,b和a相等 如图: 值...

Codeforces 1342 C. Yet Another Counting Problem(找规律)

题意: [l,r][l,r][l,r] 范围内多少个数满足 (x%b)%a!=(x%a)%b(x \% b) \% a != (x \% a) \% b(x%b)%a!=(x%a)%b。 一般这种题没什么思路就打表找一下规律。 7 8 9 10 11 12 13 14 15 16 17 18 19 20 28 29 30 31 32 33 34 35 36 37 38 39 40 41 49 50...

[笔记]飞浆PaddlePaddle-百度架构师手把手带你零基础实践深度学习-21日学习打卡(Day 3)

[笔记]飞浆PaddlePaddle-百度架构师手把手带你零基础实践深度学习-21日学习打卡(Day 3) (Credit: https://gitee.com/paddlepaddle/Paddle/raw/develop/doc/imgs/logo.png) MNIST数据集 MNIST数据集可以认为是学习机器学习的“hello world”。最早出现在1998年LeC...

哈希数据结构和代码实现

主要结构体: 实现插入、删除、查找、扩容、冲突解决等接口,用于理解哈希这种数据结构 完整代码参见github: https://github.com/jinxiang1224/cpp/tree/master/DataStruct_Algorithm/hash...