Maximum sum Sequence such that no two elements are adjacent

Правка en3, от abhi55, 2018-05-18 00:12:24

My DP implementation of max sum is below but i need sequence which is giving max sum instead of max sum value.

public int maxSum(int arr[]) {
     int excl = 0;
     int incl = arr[0];
     for (int i = 1; i < arr.length; i++) {
       int temp = incl;
       incl = Math.max(excl + arr[i], incl);
       excl = temp;
     }
     return incl;
}

So 3 2 7 10 should return (3 and 10) or 3 2 5 10 7 should return (3, 5 and 7) or {5, 5, 10, 100, 10, 5} will return (5, 100 and 5) or {1, 20, 3} will return 20 i exactly want this problem solution but return value i need is sequence of elements included in max sum instead of max sum value

Update:-no need to handle -ve elements because all elements in sequence(Array) are +ve

Теги #algorithms, #dynamic-programming

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский abhi55 2018-05-18 00:12:24 90
en2 Английский abhi55 2018-05-17 18:29:47 85
en1 Английский abhi55 2018-05-17 15:57:32 724 Initial revision (published)