longest increasing subsequence without sorting.

Question

I want to find the longest increasing subsequence without sorting it and to then sum the numbers of the period,for example like
11,1,9,25,1,66.
11,1 not increasing subsequence.
1,9,25 is an increasing subsequence consisting of 3 elements.
1,66 is increasing subsequence
consisting of 2.
so output should be the sum of 3 elements
1+9+25.
how could such a thing be done using c/c++?

Answer 1

I agree, it is much easier task for the human brain to find the answer by inspection than to teach a computer how it is done. That is why software developers get paid for what they do.

Your job is to break it down into detailed steps that mimic what your amazing brain can do. So slow down your brain and ask it to teach you, too!

Answer 2

Observe in detail how you do it manually. Then teach the computer to do the same thing.

Answer 3

Brian manually i would just look at it and then know the increasing numbers then add them, i do not think that the computer will understand only by “looking”

Answer 4

Break it down. Programs have only 3 elements:
- input
- process
- output

At each step identify the above elements.

Input is an array of integers.

Process is to find and sum the max increasing subsequence.
Loop:
Part 1:
Input is the next two integers.
Process is to compare the two
integers. If they are increasing,
increment a counter and accumulate
their sum, then advance to the next
number to repeat the process.

Output is a count of how many
elements are increasing, and the sum
of the sequence.

Part 2:
Input is the current counter and sum.

Process is to compare the current
counter with the largest counter
found so far and replace it if the
current one is larger.

Output is the larger counter (with
sum).

Re-initialize the current counter and
continue looping until end of array.

Final:
Output the max counter and sum.

Answer 5

how can i advance to the next number, and how am i going to re initialize the current counte. my whole problem is how to do this with code

Answer 6

The numbers would be stored in an array.
Loop through the array and examine each number by using its index value that you would hold in an integer variable. To advance to the next number in the array you would increment the index variable each time through the loop.

Re-initialize the counter and sum by setting those variables equal to zero.

Answer 7

int main() {

int i,sum;
int n,count;

printf("enter the size of the array\n");
scanf("%d",&n);
printf("enter the elments of the array");
int arr[1000];
for(i=1;i<n;i++)
{
scanf("%d",&arr[i]);

if(arr[i]>arr[i-1])
{
count++;
sum = arr[i]+arr[i-1];

}
else
{
i++;
}
}
is this how it should be done?

Answer 8

It is a good step forward. As you might expect, there are problems to fix.

arr[0] does not have a valid value. Consider reading it in before starting the loop.

Both count and sum start with garbage values. Initialize count to zero. Initialize sum to arr[0] (after you read it in).

In the loop, sum is adding only two values. You need to accumulate all values in the current sequence. Change it to: sum = sum + arr[i];
(or use the short version: sum += arr[i];)

Inside the else clause is where you would put the comparison and update of the longest sequence count and sum. You will need to declare and initialize two more variables to store those. Also this is where you would reset the current count and sum. Set count=0. Set sum=arr[i].

Remove i++ from the else clause. It already increments in the for() statement.

And finally of course, print out the results.