当前位置: 首页 > 知识库问答 >
问题:

查找总和小于给定值的最大元素(连续)?

有玄天
2023-03-14

所以,我有一个所有正自然数的数组。给我一个阈值。我必须找出总和小于给定阈值的数字(连续的)的最大计数。

For example, 
IP: arr = {3,1,2,1}
Threshold = 5

O/P: 3

输入数组的最大大小可以为 10^5。

基本上,我想到了一种算法,它计算原始数组的子集中元素的数量,这些元素的总和将小于给定的阈值。但是,这将导致O(N^2).的复杂性有人能建议一个更好的算法吗?我不是在寻找一个代码,只有一个算法/伪代码将做得很好。谢谢!

共有3个答案

欧桐
2023-03-14

我会尝试以下方法

  • 从数组开头的元素求和开始,直到达到阈值。将此子数组保存为临时结果。
  • 然后从子数组的开头删除一个元素,并尝试从另一侧添加新元素,直到再次达到阈值。如果结果更大,请将以下结果替换为新结果。
  • 继续直到数组结束。
陈昊昊
2023-03-14

这将有点粗糙,但应该指向一个O(n)解决方案

用两个指针遍历列表,两个指针都从一开始,我们将其中一个称为引导,另一个称之为跟踪,因为一个引导,一个跟踪。

跟踪从跟踪到领先的金额;以及当前遇到的最长有效序列的长度。

当当前总和小于(或等于)阈值时,推进领先指针并通过添加它现在指向的值来调整总和。如果总和仍然小于(或等于)阈值,则从线索到领先的顺序是可能的。

当当前总和大于阈值时,推进跟踪指针。

继续,直到引线指针到达终点。

你需要填写细节并仔细实施,但对我来说这听起来足够了。

王锐
2023-03-14
public static int maximumSum(int[] array, int t){
    int maxSum = 0;
    int curSum = 0;
    int start = 0;
    int end = 0;
    while(start < array.length){

        if(curSum > maxSum && curSum <= t){
            maxSum = curSum;
        }
        if(curSum <= t && end < array.length){
            curSum += array[end];
            end += 1;

        }
        else{
            curSum -= array[start];
            start+= 1;
        }
    }
    return maxSum;
}

此代码的复杂性是 O(2 * n),实质上是 O(n)。我想不出任何改进。

 类似资料:
  • 给定一个向量和一个有序向量,我想要一个向量,其中 ] 等于 中最小元素的索引,以便

  • 本文向大家介绍JavaScript 查找最小或最大元素,包括了JavaScript 查找最小或最大元素的使用技巧和注意事项,需要的朋友参考一下 示例 如果您的数组或类似数组的对象是numeric,也就是说,如果它的所有元素都是数字,则可以使用Math.min.apply或作为第一个参数Math.max.apply传递null,而将数组作为第二个参数传递。 6 在ES6中,可以使用...运算符扩展数

  • 我的问题很简单,但我不知道如何解决我想要的。我必须找到小于给定数字的最大数素数,如果不存在则打印消息。 代码是有效的,如果数字是10,它会打印7,但我想做2个新的修改,我找不到解决方案。例如,如果给定的数字是1,我的程序应该如何修改以打印消息?我试着写一个if-else,但是如果我用if修改了while,这将不会有帮助。第二件事,如果给定的数是素数,代码仍然会找到比给定数少的数。如果我给数字7,输

  • 这个问题有多项式解吗?如果有,你能呈现吗?

  • 我有一个对象流,我想找到一个最大值的一些属性,计算起来很昂贵。 作为一个特定的简单示例,假设我们有一个字符串列表,我们希望找到最酷的一个,给定函数。

  • 问题内容: 我有一个对象流,我想找到一个具有某些属性最大值的对象,该属性的计算成本很高。 作为一个简单的具体示例,假设我们有一个字符串列表,并且希望找到给定功能的最酷的字符串。 以下应该工作: 现在,这有两个问题。首先,假设计算起来很昂贵,这可能不是很有效。我想该方法将需要重复使用比较器,该比较器将依次重复调用,最后每个字符串将被多次调用。 其次,必须提供比较器会导致代码有些冗余。我更喜欢这样的语