given an array of positive numbers and negative numbers devise an algo to find max non-consecutive sum in that array. complexity should be in o(n).

given an array of positive numbers and negative numbers devise an algo to find max non-consecutive sum in that array. complexity should be in o(n).

s(i)=max{s(i-1),s(i-2)+a[i]} if(a[i]>0)
s(i)=s(i-1) if(a[i]<0)

int f(int* a,int n)//this is recursive way, which is O(2^n)
{
 if(n<0) return 0;
 if(a[n]>0)
  return max(f(a,n-1),f(a,n-2)+a[n]);
 return f(a,n-1);
}

int b[9]={0};
int f2(int* a,int n)//this is dp, which is O(n)
{
 if(n<0) return 0;
 if(a[n]>0)
 {
  //if(b[n-1]&&b[n-2])
  // return max(b[n-1],b[n-2]+a[n]);
  //if(b[n-1])
  // return max(b[n-1],f(a,n-2)+a[n]);
  //if(b[n-2])
   return max(f(a,n-1),b[n-2]+a[n]);
 }
 else
 {
  if(b[n-1]) return b[n-1];
  else return f(a,n-1);
 }
}

int main()
{
 int a[9]={1,-2,3,4,-1,6,5,2,4};
 cout<<f(a,8)<<endl;
}

Fibonacci series: the complexity of the recursion function is O(2^n)

Fibonacci series: the complexity of the recursion function is O(2^n)

Use dp we can reduce complexity to O(n)

int f(int num,int* a)
{
 if(num<0) return 0; 
 if(num==1){a[num]=1; return 1;}
 
 a[num]=f(num-1,a)+a[num-2];
 return a[num];
}
int main()
{
 int num=5;
 int* a=(int*) malloc(sizeof(int)*(num+1));
 for(int i=0;i<=num;i++)
  a[i]=1;
 cout << f(num,a);
}

Write a function to find the longest palindrome from a string.

Write a function to find the longest palindrome from a string.

Suppose the string is str, you reverse the str get strr, make a suffix tree for these two strings. If palindrome is like “cabbad”, for every i find LCA of suffix i of str and suffix m-i+1of strr
If palindrome is like “dacab”, for every i find LCA of suffix i of str and suffix m-i of strr
Find maximal LCA, this O(n)
or
Use dynamic programming, find longest common substring with str and strr, O(n^2)
This is not right
forward T: ABCXYYZCBA
reverse T: ABCZYYXCBA
The longest common substring is ABC, but the longest palindromic substring is just YY.

You are given an array A of size n.Give an algorithm to find i and j such that 1) i < j and 2) A[j] - A[i] is maximum among all such A[x] - A[y] where

You are given an array A of size n.Give an algorithm to find i and j such that
1) i < j and
2) A[j] - A[i] is maximum among all such A[x] - A[y] where x > y.

Intention is: given j, how to choose i in order to achieve a maximum subtraction. The answer is to choose the minimum value in A[0]..A[j-1] so that A[j]-A[i] is maximized.

int max = MIN_INT;            // max subtraction
int max_i = 0, max_j;      // max corresponding i, j
int min = A[0], min_i = 0; // min value since so far

for (int i = 1; i < n; i++) {
  if (A[i] - min > max) {
    max = A[i] - min;
    max_i = min_i;
    max_j = i;
  }
  if (A[i] < min) {
    min = A[i];
    min_i = i;
  }
}

having a string say, "foobarfoo", in which "fo" and "oo" are repeated twice. You have to find all such repeated pairs whose length is tow in O(n) time

having a string say, "foobarfoo", in which "fo" and "oo" are repeated twice. You have to find all such repeated pairs whose length is tow in O(n) time. The string can only have alphanumeric elements in it and code it in C.

Use suffix tree O(n) which is not easy to code
Use dp which is O(n^2)
Use hash table, it can be done in O(n).
Traverse the string, each time take two consecutive characters, hash them in the hashtable, the hash function is just base 36 number system

void foo(char* str)
{
 int i=0;
 int j=1;
 int hashtable[1296]={0};//36*36
 while(str[j])
 {
  int idx=(str[i]-'a')*36+(str[j]-'a');//base 36
  if(!hashtable[idx])
   hashtable[idx]=1;
  else cout<<str[i]<<str[j]<<endl;
  i++;
  j++;
 }
}