CareerCup

This should work..

public int maxSum(int[] A , int currIndex , int sum){

  if(index == A.length){
    return 0;
  }
  return  sum+max(maxSum(A,i+1,sum),A[currIndex]+max(A,i+2,sum));
}

Can you explain "max sum". An example would help.

Considering 'max sum' means subarray with maximum sum and also that this subarray is composed of alternate numbers(since two numbers should not be adjacent to each other) here is the solution I have in mind.
Split the array into two.
First array has all elements at even index, 2nd array has elements in odd index.
Then apply largest contiguous subarray sum method to both.
Return the higher one as the result

Keep two variables to store the 'max till the boundary' and 'max before the boundary'. Iterate over the elements of the array one by one and keep updating the variables. This is similar to the O(n) maximum subarray problem.

static int getMaxSubSeqNonAdjacent(int[] array) {
        int sumTillBoundary   = array[1];
        int sumBeforeBoundary = array[0];

        for (int i = 2; i < array.length; i++){
            int sumBeforeBoundary2 = sumBeforeBoundary;
            
            sumBeforeBoundary = Math.max(sumTillBoundary, sumBeforeBoundary);
            sumTillBoundary   = Math.max(sumBeforeBoundary2 + array[i], array[i]); 
        }
        
        return Math.max(sumTillBoundary, sumBeforeBoundary);
    }

This is dynamic programming question
Let S[j] be the max sum till index j
Base case, S[0] = A[0], S[1] = A[1]
S[j] = max (S[j-i] + S[i], S[j]), where i goes from [0, j-2], since it cant be adjacent elements.

The answer would be at S[n].

This is dynamic programming question
Let S[j] be the max sum till index j
Base case, S[0] = A[0], S[1] = A[1]
S[j] = max (S[j-i] + S[i], S[j]), where i goes from [0, j-2], since it cant be adjacent elements.

The answer would be at S[n].

This is dynamic programming question
Let S[j] be the max sum till index j
Base case, S[0] = A[0], S[1] = A[1]
S[j] = max (S[j-i] + S[i], S[j]), where i goes from [0, j-2], since it cant be adjacent elements.

The answer would be at S[n].

int main()
{int maxsum=0;
  
for(int j=1;j<=n;j++)
{
  for(int k=0;k<=(n-j);k++)
   {
       for (int i=k; i<=j; i++)
          sum=sum + a[i];
          if (sum>maxsum)
              maxsum=sum;
     }
   }
}

C++11:

// TASK: write a insert method for singly linked list, so that it will insert elements in the ascending order.

template <typename T>
class Node {
public:
    using Type = T;
    
    template <typename... Args>
    Node(Args&&... args) : value_(args...) {}
    
    void setNext(Node *next) {
        this->next_ = next;
    }
    
    const Node * next() const {
        return next_;
    }
    
    Node * next() {
        return next_;
    }
    
    void setValue(const Type &value) {
        this->value_ = value;
    }
    
    const Type & value() const {
        return value_;
    }
    
    Type & value() {
        return value_;
    }
    
private:
    
    enum class ConstructorType { Clone };
    
    Node(const Node &other, ConstructorType) {
        this->next_ = other.next_;
        this->value_ = other.value_;
    }
    
public:
    
    Node * clone() const {
        return new Node(*this, ConstructorType::Clone);
    }
    
private:
    
    Node *next_ = nullptr;
    Type value_;
};

template <typename T>
class List {
public:
    
    using Type = T;
    using Node = ::Node<T>;
    
    const Node * operator [](unsigned long index) const {
        Node *ptr = first_;
        while (ptr->next() && index > 0) {
            ptr = ptr->next();
            index--;
        }
        return ptr;
    }
    
    List & operator <<(Node node) {
    //    return this->operator <<(node);
    //}
    //
    //List & operator <<(Node &node) {
        if (!first_) {
            first_ = node.clone();
        } else {
            Node *ptr = first_;
            
            while (ptr->next() && ptr->next()->value() < node.value()) {
                ptr = ptr->next();
            }
            
            if (ptr != first_) {
                ptr->setNext(node.clone());
                ptr->next()->setNext(ptr);
            } else {
                ptr = node.clone();
                ptr->setNext(first_);
                first_ = ptr;
            }
            
            return *this;
        }
    }
    
    Node * first() {
        return this->first_;
    }
    
private:
    
    Node *first_ = nullptr;
};

#include <assert.h>

int main() {
    // TEST: basic usage of list
    {
        List<int> list;
        list << 3 << 2 << 1;
        Node<int> *ptr = list.first();
        assert(ptr->value() == 1);
        ptr = ptr->next();
        assert(ptr->value() == 2);
        ptr = ptr->next();
        assert(ptr->value() == 3);
        assert(ptr->next() == nullptr);
    }
    
    // TEST: operator []
    {
        List<int> list;
        list << 3 << 2 << 1;
        assert(list[0]->value() == 1);
        assert(list[1]->value() == 2);
        assert(list[2]->value() == 3);
    }
}

/crackprogramming.blogspot.com/2012/10/find-largest-contiguous-sub-array-sum.html