I want to find the longest increasing subsequence without sorting it, and to then sum the numbers of the period, for example like :
17, 18, 19, 5, 6, 23, 24, 25, 24, 25
17, 18, 19
is an increasing subsequence.5, 6, 23, 24, 25
is another increasing subsequence.
but since 5, 6, 23, 24, 25
are 5
elements and 17, 18, 19
are 3
which is less than the 5
, the output should be the sum of the longer period which is the sum of the 5
elements, 83
.
How could such a thing be done using c? I am new to C so this is all what I could think of.
#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;
}
CodePudding user response:
You really need two loops.
One that iterates through all elements. This is the "starting" index of a sequence.
Then, an inner loop that starts at one element to the right of the start. It loops to the end of the array but stops if it sees the current element is out of sequence.
After the second loop ends, the difference of these two indexes is the sequence length.
Here is some refactored code. It is annotated:
#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: %d\n",sum(maxidx,maxlen));
return 0;
}
Here is the program output:
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
UPDATE:
A [considerable] speedup for the above is to change:
for (int ilhs = 0; ilhs < count; ilhs) {
Into:
for (int ilhs = 0; ilhs < count; ilhs = irhs) {
And, move the int irhs;
above the outer loop.
This reduces the time from O(n^2) to O(n)
CodePudding user response:
Here's an outline of one possible algorithm that will solve it using one loop.
Building blocks:
- A variable that stores the number of elements in the longest sequence encountered so far, let's call it
longest_seq
. - A variable that stores the sum of the longest sequence encountered so far,
longest_sum
. - A variable for counting the length of the sequence you are currently examining,
running_seq
. - A variable keeping the sum of the current sequence,
running_sum
.
Start by initializing:
longest_seq = 0
longest_sum = 0
Then initialize the running variables to handle the first element. The way the following loop is created should make it clear why.
running_seq = 1
running_sum = arr[0]
Now to the interesting part:
- Let an index variable,
i
, loop from1
(not0
as usual, we handled the first element before the loop) to the number of elements you have inarr
, minus1
.- If
arr[i]
is greater thanarr[i-1]
(the previous element), the running sequence is still going on, so- Increase
running_seq
by1
.
- Increase
- else, if
arr[i]
is not greater thanarr[i-1]
, the running sequence is broken, so- Check if
running_seq
is greater thanlongest_seq
. If it is:- Save
running_seq
andrunning_sum
tolongest_seq
andlongest_sum
.
- Save
- Reset
running_seq = 1
andrunning_sum = 0
.
- Check if
- Unconditionally add
arr[i]
torunning_sum
- If
When the loop is done, you need to check if running_seq
is greater than longest_seq
again (and save the values in case it is) just in case the longest sequence happened to be at the end of the array.
The answers when this is done are in longest_seq
and longest_sum
.