如何在不排序的情况下找到增长最长的子序列

Question

我想在不排序的情况下找到最长的递增子序列，然后对周期的数字求和，例如：

12, 15, 16, 4, 7, 10, 20,25

• 12,15,16是一个递增子序列
• CCD_ 2是另一个递增子序列

但是由于4,7,10,20,25是5元素并且12,15,16是小于4的3，所以输出应该是较长周期的总和，该较长周期是5元素的总和66。

用c怎么能做这样的事？我是C的新手，所以这就是我所能想到的。

#include<stdio.h>
int main() {
int count = 0;
int n;
int max = 0;
scanf("%d", &n);
int arr[1000];
for(int i = 0;i<n;i++){
if(arr[i+1>arr[i])
count++;
if(count>max)
max = count;
}

Answer 1

您确实需要两个循环。

遍历所有元素的一个。这就是"；启动"；序列的索引。

然后，从起点右侧的一个元素开始的内部循环。它循环到数组的末尾，但如果发现当前元素不按顺序，则停止。

第二个循环结束后，这两个索引的差值就是序列长度。

---

以下是一些重构的代码。注释：

#include <stdio.h>
int arr[] = { 17, 18, 19, 5, 6, 23, 24, 25, 24, 25, 17, 18, 19 };
// show -- print a sequence
void
show(int begidx,int count,const char *tag)
{
printf("%s: %d %d --",tag,begidx,count);
for (;  count > 0;  --count, ++begidx)
printf(" %d",arr[begidx]);
printf("n");
}
// sum -- get sum of the sequence
int
sum(int begidx,int count)
{
int sum = 0;
for (;  count > 0;  --count, ++begidx)
sum += arr[begidx];
return sum;
}
int
main(void)
{
int count = sizeof(arr) / sizeof(arr[0]);
int maxlen = 0;
int maxidx = -1;
show(0,count,"ORIG");
// loop through all possible starting points for sequence
for (int ilhs = 0;  ilhs < count;  ++ilhs) {
int lval = arr[ilhs];
// loop through all numbers to the right of the starter
// stop at the array end or when we get a number that is out of sequence
int irhs;
for (irhs = ilhs + 1;  irhs < count;  ++irhs) {
int rval = arr[irhs];
// out of sequence -- we've hit the end
if (rval < lval)
break;
lval = rval;
}
// get length of the sequence we just saw
int curlen = irhs - ilhs;
// remember a larger sequence
if (curlen > maxlen) {
maxlen = curlen;
maxidx = ilhs;
show(maxidx,maxlen,"NEW");
}
}
// show the maximum sequence
show(maxidx,maxlen,"FINAL");
// sum the sequence
printf("SUM: %dn",sum(maxidx,maxlen));
return 0;
}

---

这是程序输出：

ORIG: 0 13 -- 17 18 19 5 6 23 24 25 24 25 17 18 19
NEW: 0 3 -- 17 18 19
NEW: 3 5 -- 5 6 23 24 25
FINAL: 3 5 -- 5 6 23 24 25
SUM: 83

---

更新：

上述情况的[相当大]加速将发生变化：

for (int ilhs = 0;  ilhs < count;  ++ilhs) {

进入：

for (int ilhs = 0;  ilhs < count;  ilhs = irhs) {

然后，将int irhs;移动到外循环上方。

这减少了从O(n^2(到O(n(的时间

Answer 2

这里概述了一种可能的算法，该算法将使用一个循环来解决问题。

构建块：

• 一个变量，存储迄今为止遇到的最长序列中的元素数量，我们称之为longest_seq
• 一个变量，用于存储迄今为止遇到的最长序列longest_sum的总和
• 用于计算当前正在检查的序列长度的变量running_seq
• 一个保持当前序列的和的变量，running_sum

通过初始化开始：

• longest_seq = 0
• longest_sum = 0

然后初始化正在运行的变量以处理第一个元素。创建以下循环的方式应该清楚地说明原因。

• running_seq = 1
• running_sum = arr[0]

现在进入有趣的部分：

• 让索引变量i从4,7,10,200(而不是像往常一样的0，我们在循环之前处理了第一个元素(循环到arr中的元素数量减去1。
  • 如果arr[i]大于arr[i-1](前一个元素(，则运行序列仍在继续，因此
    • 将running_seq增加1
  • 否则，如果arr[i]而不是大于arr[i-1]，则运行序列将中断，因此
    • 检查running_seq是否大于longest_seq。如果是：
      • 将running_seq和running_sum保存到longest_seq和longest_sum
    • 重置running_seq = 1和running_sum = 0
  • 无条件地将arr[i]添加到running_sum

循环完成后，您需要再次检查running_seq是否大于longest_seq(如果是，则保存值(，以防最长的序列恰好位于数组的末尾。

完成此操作时的答案在longest_seq和longest_sum中。

演示实现

---

一个有微小差异的变体是关于running_sum:的更新稍微改变循环

• 让索引变量i从1(而不是像往常一样的0，我们在循环之前处理了第一个元素(循环到arr中的元素数量减去1。
  • 如果arr[i]大于arr[i-1](前一个元素(，则运行序列仍在继续，因此
    • 将running_seq增加1
    • 将arr[i]添加到running_sum
  • 否则，如果arr[i]小于em>而不是大于arr[i-1]，则运行序列将中断，因此
    • 检查running_seq是否大于longest_seq。如果是：
      • 将running_seq和running_sum保存到longest_seq和longest_sum
    • 重置running_seq = 1和running_sum = arr[i]

演示实现