Longest Increasing Subsequence

// INPUT = {5,8,0,3,1,9,2,4}
// OUTPUT - Length of LIS = 4 {0,1,2,4} //prints only length
// Complexity - O(n^2)
// If anyone knows about the O(nlogn) solution, feel free to
// mention it in comments section

#include<stdio.h>
#include<stdlib.h>

int maxL(int *L,int i,int a[]){
int max = 0;
int j;
for(j=0;j<i;j++){
if(a[j] < a[i] && L[j] > max){
max = L[j];
}
}
return max;
}

int lis(int a[],int n){
int *L = (int *)malloc(sizeof(int)*n);
int i;
int lis = 1;
for(i=0;i<n;i++){
L[i] = maxL(L,i,a)+1;
}
for(i=0;i<n;i++){
if(L[i] > lis){
lis = L[i];
}
}
return lis;
}

int main(){
int a[] = {5,8,0,3,1,9,2,4};
int l = lis(a,sizeof(a)/sizeof(int));
printf("length of LIS = %d",l);
return 0;
}

Buy and Sell Stocks

You have an array for which ith element is the price of a given stock on day i.
If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best time to buy and sell.

#include<stdio.h>

void maxProfit(int a[], int len){
int buy=0;
int sell=0;
int profit = 0;
int minSoFar = 0;
int i;
for(i=1;i<len;i++){
if(a[i] < a[minSoFar]){
minSoFar = i;
}
if(a[i] - a[minSoFar] > profit){
profit = a[i] - a[minSoFar];
buy = minSoFar;
sell = i;
}
}
printf("If you buy on day %d and sell on %d, you profit will be %d\n",buy,sell,profit);
}

int main(){
int a[] = {4,2,5,6,1,6,4};
maxProfit(a,sizeof(a)/sizeof(int));
return 0;
}

Maximum contiguous sum in Circular Array

// find max contiguous sum in circular array
// INPUT : {8,-8,9,-9,10,-11,12} OUTPUT : 22
// INPUT : {1,-1,2,-1,1} OUTPUT : 3

#include<stdio.h>
#include<stdlib.h>

int findMaxContSum(int A[],int len){
int i,c,max;
for(i=0;i<len;i++){
//printf("%d\n",A[i]);
}
int *S = (int *)malloc(sizeof(int)*len);
int *start = (int *)malloc(sizeof(int)*len);
for(i=0;i<len;i++){
start[i] = -1;
}
S[0] = A[0];
start[0] = 0;
for(i=1;;i=(i+1)%len){
c = (i-1+len)%len;
if(start[i] == start[c]){
break;
}
if(S[c] + A[i] > A[i]){
S[i] = S[c] + A[i];
start[i] = start[c];
} else {
S[i] = A[i];
start[i] = i;
}
}
max = S[0];
for(i=1;i<len;i++){
if(S[i] > max){
max = S[i];
}
}
free(start);
free(S);
return max;
}

int main(){
//int A[] = {8,-8,9,-9,10,-11,12};
int A[] = {1,-1,2,-1,1};
int max = findMaxContSum(A,sizeof(A)/sizeof(int));
printf("%d",max);
return 0;
}