The task is to find the maximum sum of a subsequence of integers from a given list. The subsequence must follow two conditions:
1)It must be contiguous, meaning the selected elements are in consecutive order from the original list.
2)At most one element can be skipped consecutively. In other words, no more than one element can be skipped in a row.
For example, if given the list [-3, 2, 4, -1, -2, -5], the maximal sum can be obtained by selecting [2, 4, -2], resulting in a sum of 4.
In another example, for the list [9, -1, -3, 4, 5], the maximum sum is 17.
public static void main(String[] args) {
int[] arr={9,-1,-3,4,5};
int n=arr.length;
System.out.print(solve(n-1,arr,0));
}
public static int solve(int ind,int[] arr,int skip){
if(ind==-1 && skip==0)
return arr[ind+1];
if(ind==-1 && skip==1)
return 0;
if(skip>1)
return Integer.MIN_VALUE;
int notpick=0;
int pick=arr[ind]+solve(ind-1,arr,0);
if(skip<2)
notpick=solve(ind-1,arr,skip+1);
return Math.max(pick,notpick);
}
i tried in a recursive approach,from the above i was able to succeed first example,but getting different output for second example i.e for the array [9, -1, -3, 4, 5].iam getting 26 as output instead of 17.what’s wrong in my approach.is my entire logic is wrong?what changes should be done?
Vahaid Sk is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.