Does not work with negative nos.
@ Yan Wang,@Adam it worked for ur inputs.
With the input like a= {10,0,0,0}, k = 2
it will give 0, 0 as output.
-----Code-----
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class NondecreasingMaxsum {
// With recursion.
public static int nondecreasingMaxsum(int [] a, int last, int pos, int
k, int sum, int[] reqArr){
if(k<=0 || pos >= a.length || k>= a.length){
return 0;
}
if(k==1){
int max =0;
for(int i=pos;i<a.length; i++){
if(a[i]>=last){
if(max<a[i]){
max = a[i];
}
}
}
if(max==0){
return 0;
}
reqArr[reqArr.length-k]= max;
return (sum + max);
}
if(a[pos]<last){
return nondecreasingMaxsum(a, last, pos + 1,k , sum, reqArr);
}
int p = nondecreasingMaxsum(a, last, pos + 1,k , sum, reqArr);
int q = nondecreasingMaxsum(a, a[pos], pos + 1, k -1, sum + a[pos],
reqArr);
if(q>p){
reqArr[reqArr.length-k]= a[pos];
}
return max(p,q);
}
public static int max(int a, int b){
return a>b?a:b;
}
public static void main(String[] args) {
int[] a = {10,5,4,11,19,6,7,3,2,19,9,8};
int k =2;
int[] reqArr = new int[k];
System.out.println(nondecreasingMaxsum(a,0,0,k,0,reqArr));
for(int i:reqArr){
System.out.println(i);
}
}
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
