最长正和子串

本文介绍了最长正和子串的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 我想知道如何获得序列中最长的正和子序列：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; } 我们对输入数组 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，那么我们知道我们将找到（或已经找到）总和> = 0的子数组，那么我们只需要比较 ba 具有先前找到的长度。否则，没有子数组以 a 开头并遵守我们的约束，因此我们需要递增 a 。 we are operating on input array A of size nLet'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 pointbecause 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. 这篇关于最长正和子串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！