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