algorithm - 最长正和子串

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

例如，我有-6 3 -4 4 -5，因此最长的正子序列是3 -44。实际上，总和为正(3)，我们既不能将-6也不能相加-5，否则它将变成消极的。

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

你有什么主意吗？

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

EDIT2:很抱歉，如果我使用“sebsequence”一词引起困惑，正如@beaker指出的那样，我的意思是子字符串

最佳答案

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

  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;
  }

我们正在对大小为A

的输入数组n进行操作

让我们定义P数组为包含前缀和的数组，直到索引i为止，这样P[i] = sum(0,i)其中`i = 0,1，...，n-1'

请注意，如果u < v和P[u] <= P[v]，那么u将永远不是我们的终点

由于上述原因，我们可以定义Q数组，该数组具有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，那么我们知道我们将找到(或已经找到)sum> = 0的子数组，那么我们只需要将b-a与先前找到的长度进行比较即可。否则，没有子数组以a开头并遵守我们的约束，因此我们需要增加a。

关于algorithm - 最长正和子串，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28356453/