Finding Max Value Of A +- A[I]

I have finals coming up next week, and I'm going over old notes and homeworks/exams trying to study. On my second homework I have a question that I got wrong and I'm just not sure what exactly to do. Here's the problem:

Design efficient algorithms that take an array of positive numbers 'a', and determine: a. the maximum value of a[j] + a[i], with j > or = to i. b. the maximum value of a[j] - a[i], with j > or = to i.

I don't want actual code, just some pseudo code and the running time of it.

What I thought would work:

Find the first, second, and third max and min values. Then do: a. first max a(j) + second max a(i), for j>=i. b. first max a(j) - first min a(i), for j>=i

And then just repeat with second max,min if above condition fails.

I don't know why I can't wrap my head around this. I know j can be equal to i, so my answer would yield the incorrect result for part a. For part b, let's say I had an array [89|90|1|2|3|4|5], it would go 90 - 1 = 89 but it should be 5 - 1 = 4. I didn't even try to think about the run time yet since that part is wrong.

Any help or hints would be great. Thank you!

Answers


a. a[j] + a[i] is straight forward , it is just 2*maximum because j can be equal to i can be done in O(N)

b. a[j] - a[i] for this case we need bit of dynamic programming to get it in O(N). Here is a way to do it in O(N):-

Build up an array such that max[i] denotes maximum element in subarray a[i to n]

 max[n] = a[n]        
 for(i=n-1;i>=1;i--) 
    max[i] = maximum(max[i+1],a[i]);

then find maximum value (max[i]-a[i]) for all i that will be your max a[j]-a[i].

Edit: Just realized that donot need to maintain array max[] you can calculate max[i] - a[i] while evaluating max[i] using just previous value.


a. to maximum a[i]+a[j] is to find the largest and second largest value in the array, it is straightforward and the time complexity is O(N).

b. To maximum a[j]-a[i] (j>=i), for each j the possible optimal solution would the a[j] - the minimum value before j, so you just need to keep this value and update the best solution

mmin = a[0];
ans = 0;
for (int j = 0; j < length(a); ++j){
    mmin = min(a[j], mmin);
    ans = max(ans, a[j] - mmin);
}
return ans;

It is also O(N).


Need Your Help

CMD.EXE batch script to display last 10 lines from a txt file

batch-file scripting cmd

Any ideas how to echo or type the last 10 lines of a txt file?

Are there any basic examples of Rack::Session::Cookie usage?

ruby passenger rack

I can't find any simple examples for using Rack::Session::Cookie and would like to be able to store information in a cookie, and access it on later requests and have it expire.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.