Algorithm PLEASE help :)
Hi I'm new in Java and I need to find algorithm for these questions :
1. Write a program that reads a number n and sequence of n numbers and finds in the sequence the longest area of adjacent equal elements . Example :
n = 14
sequence = {7,3,3,3,7,7,7,7,3,3,3,2,7,2}
result = {7,7,7,7}
2. Write a program that reads from the console a sequence of numbers and finds the longest subsequence of growing numbers. Example :
sequence = {3, 1, 2, 4, 6, 2, 3, 5, 4, 5}
result = {1, 2, 3, 4, 5}
I'll be very thankful if you write me one of the algorithms
[605 byte] By [
n3m0a] at [2007-11-27 1:21:38]
# 6
Construct a map of the longest sequences with the least last added value, so if you have
6421
321
And encounter 5, you find 321 in lgM, where M is the size of the table, insert 5321, but when inserting it look at the next greater node, see whether it's the same length, and remove it if so, as any value which would extend it would also extend the sequence with the lower last added value you just added. Adjacent nodes must be be one number longer, otherwise there would be an intermediate sequence. You also look at the next least sequence, and if it's last value is your value -1 then delete it, as there can't be a sequence which extends it by one which has a lower next value:
6421
321
+5 =>
6421
+5321
321
eliminate above as same length (above will always be same length, if you've added one value to the longest sequence whose last added value is less than the new value)
=>
5321
321
+4 =>
5321
+4321
321
eliminate above, and eliminate below as consecutive values
=>
4321
So that would be O(N lgM), where M is the maximum size of the table. You can also reject any values less than or equal to the last value in the least long sequence as they won't contribute, so run time will typically be better, but I'm not about to calculate by how much. You do need to maintain all of the best sequences whose last value is less than a value which can be extended to be longer than any other sequence extended by adding a given new value, so I don't think O(N) is possible. If you have two numbers remaining, you don't know to choose between 54321 and 754321 until you get 6,7 or 8,3. The question is what size M is - if the sequence is increasing by one each time, M=1. If it's the same value repeated, or decreasing, M=1. For the sample input sequence, M gets up to 3:
+3 = {3}
+1 = {3},{1} -> {1}
+2 = {2,1},{1} -> {2,1}
+4 = {4,2,1},{2,1}
+6 = {6,4,2,1},{4,2,1},{2,1}
+2 = {6,4,2,1},{4,2,1},{2,1}
+3 = {6,4,2,1},{4,2,1},{3,2,1},{2,1} -> {6,4,2,1},{3,2,1}
+5 = {6,4,2,1},{5,3,2,1},{3,2,1} -> {5,3,2,1},{3,2,1}
+4 = {5,3,2,1},{4,3,2,1},{3,2,1} -> {4,3,2,1}
+5 = {5,4,3,2,1},{4,3,2,1} -> {5,4,3,2,1}
Since M is increased for every value encountered greater than the previous greatest value, and decreased for every value adjacent to an existing value. You'd need to know the range of possible values to determine it, but at worst case M = N for sequences such as a[i] = 2*i.
