最长正和子串 [英] Longest positive sum substring

问题描述

我想知道如何获得序列中最长的正和子序列：

I was wondering how could I get the longest positive-sum subsequence in a sequence:

例如，我有-6 3 -4 4 -5，因此正子序列的最长正数是3 -4 4.实际上，总和是正数（3），我们不能将-6都不加-5否则它就不会变成负数。

For example I have -6 3 -4 4 -5, so the longest positive subsequence is 3 -4 4. In fact the sum is positive (3), and we couldn't add -6 neither -5 or it would have become negative.

在O（N ^ 2）中可能很容易解决，我认为它可以更快地存在，例如在O（NlogN）中

It could be easily solvable in O(N^2), I think could exist something much more faster, like in O(NlogN)

？

编辑：必须保留顺序，并且您可以从子字符串中跳过任何数字

the order must be preserved, and you can skip any number from the substring

EDIT2：很抱歉，如果我使用术语 sebsequence引起了困惑，正如@beaker指出的，我的意思是子字符串

I'm sorry if I caused confusion using the term "sebsequence", as @beaker pointed out I meant substring

推荐答案

O（n）时空解决方案，将从代码（对不起，Java ;-）开始，并在稍后尝试进行解释：

O(n) space and time solution, will start with the code (sorry, Java ;-) and try to explain it later:

  public static int[] longestSubarray(int[] inp) {
    // array containing prefix sums up to a certain index i
    int[] p = new int[inp.length];
    p[0] = inp[0];
    for (int i = 1; i < inp.length; i++) {
      p[i] = p[i - 1] + inp[i];
    }

    // array Q from the description below
    int[] q = new int[inp.length];
    q[inp.length - 1] = p[inp.length - 1];
    for (int i = inp.length - 2; i >= 0; i--) {
      q[i] = Math.max(q[i + 1], p[i]);
    }

    int a = 0;
    int b = 0;
    int maxLen = 0;
    int curr;
    int[] res = new int[] {-1,-1};
    while (b < inp.length) {
      curr = a > 0 ? q[b] - p[a-1] : q[b];
      if (curr >= 0) {
        if(b-a > maxLen) {
          maxLen = b-a;
          res = new int[] {a,b};
        }
        b++;
      } else {
        a++;
      }
    }
    return res;
  }

• 我们对输入数组<$ c进行操作$ c> A 大小为 n


• 让我们定义数组 P 作为包含前缀和直到索引 i 的数组，因此 P [i] = sum（0，i）其中`i = 0,1，...，n-1'


• 请注意，如果 u< v 和 P [u]< = P [v] 则 u 永远不会是我们的终点


• 由于上述原因，我们可以定义一个数组 Q ，其中数组<< c $ c> Q [n- 1] = P [n-1] 和 Q [i] = max（P [i]，Q [i + 1]）


• 现在让我们考虑 M_ {a，b} ，它向我们显示了从 a开始的最大总和子数组，结束于 b 。我们知道 M_ {0，b} = Q [b] ，并且 M_ {a，b} = Q [b]-P [a -1]


• 有了以上信息，我们现在可以初始化 a，b = 0 并开始移动它们。如果 M 的当前值大于或等于0，那么我们知道我们将找到（或已经找到）总和> = 0的子数组，那么我们只需要比较 ba 具有先前找到的长度。否则，没有子数组以 a 开头并遵守我们的约束，因此我们需要递增 a 。


• we are operating on input array A of size n
• Let's define array P as the array containing the prefix sum until index i so P[i] = sum(0,i) where `i = 0,1,...,n-1'
• let's notice that if u < v and P[u] <= P[v] then u will never be our ending point
• because of the above we can define an array Q which has Q[n-1] = P[n-1] and Q[i] = max(P[i], Q[i+1])
• now let's consider M_{a,b} which shows us the maximum sum subarray starting at a and ending at b or beyond. We know that M_{0,b} = Q[b] and that M_{a,b} = Q[b] - P[a-1]
• with the above information we can now initialise our a, b = 0 and start moving them. If the current value of M is bigger or equal to 0 then we know we will find (or already found) a subarray with sum >= 0, we then just need to compare b-a with the previously found length. Otherwise there's no subarray that starts at a and adheres to our constraints so we need to increment a.

这篇关于最长正和子串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！