You have an array of integers:
int[] A = { 10, 3, 6, 8, 9, 4, 3 };
My goal is to find the largest difference between A[Q] and A[P] such that Q > P.
If P = 1 and Q = 4
diff = A[Q] – A[P]
diff = 9 – 3
diff = 6
Since 6 is the largest number between all the difference, that is the answer.
Solution:
public int solution(int[] A, int N)
{
if (N < 1) return 0;
int max = 0;
int result = 0;
for(int i = N-1; i >= 0; --i)
{
if(A[i] > max)
max = A[i];
int tmpResult = max - A[i];
if(tmpResult > result)
result = tmpResult;
}
return result;
}
Time Complexity: O(N)
nt[] x= {4,10,14,8,1,0,3,6,4,8,9,10};
int max=0;
int maxT=0;
int len= x.length-1;
for (int i=len; i>=0; i–){
for (int j=0; j<len; j++)
{ if (( x[i]>x[j])&& (i>j))
{ maxT=x[i]-x[j];
if (maxT> max){
max=maxT;
System.out.println("a["+i+"]" + " – " + "a["+ j+ "]" + " = " + max);
}
}
}
}
//Takes in array as input
static void maxDiff(int a[]){
int max = 0;
int pPos = 0;
int qPos = 0;
for (int i = 0; i < a.length -1 ; i++) {
for (int j = i + 1; j max){
max = a[j] – a[i];
qPos = j;
pPos = i;
}
}
}
System.out.println(” Max Difference : – “+max + ” Q : “+qPos + ” P : “+pPos);
}
Also for max sum :-
static void maxSum(int a[]){
int max = 0;
int pPos = 0;
int qPos = 0;
for (int i = 0; i < a.length -1 ; i++) {
for (int j = i + 1; j max){
max = a[j] + a[i];
qPos = j;
pPos = i;
}
}
}
System.out.println(” Max Sum : – “+max + ” Q : “+qPos + ” P : “+pPos);
}
Complexity O(N2)