连续子序列求和的最大值
程序员文章站
2022-03-06 18:04:28
...
输入一个整数序列(浮点数序列也适合本处讲的算法),求出其中连续子序列求和的最大值。
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;
}
下一篇: 温故而知新:5个最难回答的Java面试题
推荐阅读
-
SQL Server 2008 R2——查找最小nIndex,nIndex存在而nIndex+1不存在 求最小连续数组中的最大值
-
Ruby实现的最长公共子序列算法
-
Python的Django REST框架中的序列化及请求和返回
-
剑指offer41:所有和为S的连续正数序列,例如,有多少种连续的正数序列的和为100
-
python实现寻找最长回文子序列的方法
-
Python针对给定字符串求解所有子序列是否为回文序列的方法
-
Python语言描述最大连续子序列和
-
【线性 dp】A005_LC_不同的子序列(记忆化 / dp 分类讨论)
-
python数据处理,连续相同的标签取最大值
-
Python语言描述连续子数组的最大和