I was doing a problem in Recursion Challenge - I. (problem link), and I comes up with an algorithm, but its not accepting my solution. Can someone please tell me where is the flaw.
Problem Description: You are given an array A of size N. You have to find the maximum fluctuation in the array.
Fluctuation = max (A[j]-A[i]) for all i,j satisfying 1 ≤ i < j ≤ N.
NOTE: fluctuation can be negative.
Constraints: 2 ≤ N ≤ 1000, 0 ≤ A[i] ≤ 10^9
My Algorithm (considering 1-based indexing)
function solve (N):
max_difference = a-a
smallest = a
for index in 2 to N:
max_difference = max(max_difference, a[index]-smallest)
if (max_difference < a[index]-a[index-1])
max_difference = a[index]-a[index-1]
smallest = a[index-1]
Please help guys.
the mistake is in the line smallest=a[index-1]
instead it should be if(a[index]<smallest) smallest=a[index];
because the variable smallest holds the smallest value in array a from 1 to index.
You can also check my code http://www.codechef.com/viewsolution/6002802
Simple Solution is:
Hope you got it!
Check your output for this test case:
4 15 3 1 9 11 17 5 12
This Code: http://www.codechef.com/viewsolution/6005001
gives output 13 where as actual answer should be 16.
But in that if block, I am calculating new max_difference according to that value i.e. a[index] - a[index-1]. So, new smallest will be a[index-1] indeed???
Can you give me a test case, where it fails?
@saanc I got your point, and I appreciate that. But I want to know the flaw in my logic/algorithm. Can you help me in that, or provide a test case where it fails. Thanx anayways.