Блог пользователя abhi55

Maximum sum Sequence such that no two elements are adjacent
Автор abhi55, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится -14 Проголосовать: не нравится

You can backtrack your DP solution.

→ Ответить
»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

you can try record the sources when you are doing you DP

for example

pos :  1  2  3  4  5  6  7

arr : 10  2  1  8  4  6 10

dp  : 10  2 11 18 15 24 28

from:  0  0  1  1  3  4  4

and looking at the result you find out that dp[7] is the maximum value you got

so go backtracking from 7

now=7;

while(now!=0){

    ans.push_back(val[now]);

    now=from[now];

}

tell me if there is any thing that you can't understand

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    dp array is wrong because max value we can achieve in this test case is 28 by using sequence 10 8 10 which equals to 28 so 10 1 4 10 will be wrong sequence

    → Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    how will we track included elements in sequence. you added indexes but are they included elements indices only?

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      sorry but I can't understand your question

      what do u mean "included elements" ,"sequence u added indexes"

      is it the backtracking step or the dp step?

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        my question is that if take sequence like 3 2 7 10 i want sequence with maximum sum as output(printed) with only condition that in sequence no adjacent element taken. and in time complexity O(n).

        → Ответить
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          yes

          and thats what i have done

          by DP and backtracking

          → Ответить
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          for the DP , hold a value MAX for the max value that you can dp from

          simultaneously , record the index of where the MAX value come from

          do you need a code for better understanding ?

          → Ответить
»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

here you are

#include <stdio.h>
const int N=1e6+10;
int main(){
    int n,dp[N],val[N],max,from[N],max_index;
    bool minus[N];
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&val[i]);
        if(val[i]<0){       //just don't take negative elements
            val[i]=0;
            minus[i]=true;
        }
        else minus[i]=false;
    }
    dp[1]=val[1];   // there is no elements to take before 1
    dp[2]=val[2];   //
    from[1]=0;
    from[2]=0;
    max=dp[1];
    max_index=1;
    for(int i=3;i<=n;i++){
        dp[i]=val[i]+max;
        from[i]=max_index;
        if(dp[i-1]>max){    //cause for the element i+1 ,the right most element you can take is i-1
            max=dp[i-1];
            max_index=i-1;
        }
    }
    if(dp[n]>max)max_index=n;
    while(max_index!=0){
        if(!minus[max_index])printf("%d ",val[max_index]);
        max_index=from[max_index];
    }
    printf("\n");
}
→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    i compiled and run code and it is giving output 3221225725 always without taking any input value and dont handle -ve elements because elements in array are +ve

    → Ответить