# 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!

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).

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

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?

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.