最近我参加了一家公司的面试,他们要求我编写一个算法,以查找数组中元素和最大的子序列。数组中的元素可以是负数。是否有O(n)的解决方案?非常感谢任何好的解决方案。
最近我参加了一家公司的面试,他们要求我编写一个算法,以查找数组中元素和最大的子序列。数组中的元素可以是负数。是否有O(n)的解决方案?非常感谢任何好的解决方案。
如果你想要最大的连续数字和,那么类似这样的代码可能有效:
$cur = $max = 0;
foreach ($seq as $n)
{
$cur += $n;
if ($cur < 0) $cur = 0;
if ($cur > $max) $max = $cur;
}
那只是我随便想到的,但看起来是正确的。(忽略它假设0是空和所有负集的答案。)
编辑:
如果你还想要序列位置:
$cur = $max = 0;
$cur_i = $max_i = 0;
$max_j = 1;
foreach ($seq as $i => $n)
{
$cur += $n;
if ($cur > $max)
{
$max = $cur;
if ($cur_i != $max_i)
{
$max_i = $cur_i;
$max_j = $max_i + 1;
}
else
{
$max_j = $i + 1;
}
}
if ($cur < 0)
{
$cur = 0;
$cur_i = $i + 1;
}
}
var_dump(array_slice($seq, $max_i, $max_j - $max_i), $max);
可能有更简洁的方法来实现它。同样,它具有相同的假设(至少有一个正整数)。另外,它只能找到第一个最大的序列。
编辑:将其更改为使用max_j
(不包括)而不是max_len
。
#include <stdio.h>
int main(void) {
int arr[] = {-11,-2,3,-1,2,-9,-4,-5,-2, -3};
int cur = arr[0] >= 0? arr[0] : 0, max = arr[0];
int start = 0, end = 0;
int i,j = cur == 0 ? 1 : 0;
printf("Cur\tMax\tStart\tEnd\n");
printf("%d\t%d\t%d\t%d\n",cur,max,start,end);
for (i = 1; i < 10; i++) {
cur += arr[i];
if (cur > max) {
max = cur;
end = i;
if (j > start) start = j;
}
if (cur < 0) {
cur = 0;
j = i+1;
}
printf("%d\t%d\t%d\t%d\n",cur,max,start,end);
}
getchar();
}
O(n)
的解决方案。O(NlogN)
时间内对其进行排序,然后找到已排序数组和原始数组的LCS
,这需要O(N^2)
时间。LCS
,它也需要O(N^2)
的时间,你可以在这里看到。O(N)
的时间内完成。void longsub(int a[], int len) {
int localsum = INT_MIN;
int globalsum = INT_MIN;
int startindex = 0,i=0;
int stopindex = 0;
int localstart = 0;
for (i=0; i < len; i++) {
if (localsum + a[i] < a[i]) {
localsum = a[i];
localstart = i;
}
else {
localsum += a[i];
}
if (localsum > globalsum) {
startindex = localstart;
globalsum = localsum;
stopindex = i;
}
}
printf ("The begin and end indices are %d -> %d (%d).\n",startindex, stopindex, globalsum);
}
sum
和MaxSum
。
我们将继续向总和中添加值,并将其与MaxSum进行比较,如果总和的值大于MaxSum,则将总和值分配给MaxSum
如果在过程中总和的值低于0,我们将重置总和并从下一个索引开始添加新数字。以下是上述解决方案的示例代码:
private static void FindMaxSum(int[] array)
{
int sum = 0;
int MaxSum = 0;
for (int i = 0; i < array.Length; i++)
{
sum += array[i];
if (sum > MaxSum)
{
MaxSum = sum;
}
else if (sum < 0)
{
sum = 0;
}
}
Console.WriteLine("最大总和为:" + MaxSum);
}
解决这个问题的第二种方法是我们将遍历数组中的每个元素。我们将使用相同的2个变量sum和MaxSum。
首先,我们将比较总和与下一个数组元素以及总和本身的加法。无论哪个更大 - 那个值将存储在总和变量中。
接下来,我们将比较总和和MaxSum的值,谁的值更大 - 我们将把该值保存在MaxSum变量中。 示例代码如下:
private static void FindMaxSum(int[] array)
{
int sum = array[0], Maxsum = array[0];
for (int i = 1; i < array.Length; i++)
{
sum = Max(sum + array[i], array[i]);
Maxsum = Max(sum, Maxsum);
}
Console.WriteLine("最大总和为:" + Maxsum);
}
private static int Max(int a, int b)
{
return a > b ? a : b;
}
由于我们需要找到最大子序列和,我们可以:
sum
和maxSum
。n
的长度。sum > maxSum
时更新maxSum
。Java
代码片段如下:
Arrays.sort(a, Collections.reverseOrder());
int sum = 0;
for (int i = 0; i < a.length; i++) {
sum = sum + a[i];
if (sum > maxSum)
maxSum = sum;
}
System.out.println(maxSum);
时间复杂度:O(nlogn)
C函数长这样:
int largest(int arr[], int length)
{
int sum= arr[0];
int tempsum=0;
for(int i=0;i<length;i++){
tempsum+=arr[i];
if(tempsum>sum)
sum=tempsum;
if(tempsum<0)
tempsum=0;
}
return sum;
}
暴力破解:使用嵌套循环找到所有可能的和,并在找到比先前设置的maxSum值更大的和时更新maxSum。时间复杂度为O(n^2)。
动态规划解决方案:这是一个非常优雅的解决方案,我在StackOverflow上发现了它本身-https://dev59.com/gV7Va4cB1Zd3GeqPMK8w#8649869v- 时间复杂度:O(n), 空间复杂度:O(n)
无需记忆的DP-Kadane算法-https://en.wikipedia.org/wiki/Maximum_subarray_problem - 时间复杂度:O(n),空间复杂度:O(1)
分治解决方案-http://eecs.wsu.edu/~nroy/courses/CptS223/notes/MaxSubsequenceSum.pdf 时间复杂度:O(nlgn)