"Coding is just like talking to a unknown girl. Once you talked to her with guts, the next time you'll never afraid",Really? Yes , try it Now !!! Everything here is for education and learning purpose only , individual holds rights on outer posts/links etc. Team Cracking The Code
#include<stdio.h>
#define MAX(a,b) ((a>b)?(a):(b))
main()
{
int arr[]={-2, -3, 4, -1, -2, 1, 5, -3};
int len,i;
int max=0;
len = sizeof(arr)/sizeof(arr[0]);
max=arr[0];
int finalmax=0;
int start=0,end=0;
for(i=1;i<len;i++)
{
max = MAX(max+arr[i], arr[i]);
finalmax=MAX(max,finalmax);
}
printf("MAX:%d %d %d \n",finalmax, start ,end);
}
Example if you want to print array http://codepad.org/BhYxSlp4
possible subsequences. Computing the sum of a subsequence takes O(n) in the worst-case. Hence, the running time of the algorithm would be 
.
by being a bit more clever in computing the sums of different subsequences. We observe that the sum of the subsequence A[i ... j+1] = A[j+1] + sum of the subsequence A[i ... j].
.![S[k]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_v4plpzZV_6v_haBaPN6s0o3S3wfKrHAvU4dgmy2LIuFHlHRVlUkxYDMua914nhzIVFKViJbPzHdUMtcN-biVLirrljPAfNUqVQNbm7SEIgQsKFFATZ36LefRafpvO_KuZKjrig=s0-d "S[k]")
denote the sum of a maximum sum contiguous subsequence ending exactly at index 
.![S[k+1] = max \{S[k] + A[k+1], A[k+1] \}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vxvbro2EaDi-E29jLsQ-a3MT2Rjbx184mGN2FoGni6wLMoeFuemxLOH3kyWXlJCHGGAYxCrQ0FxOjQOhKrHB3Cu-AWHNNHhQ10ErUtBi2tzDtwU4ppkL3XmP-2Fp5jcP7rwYwnNoIqxTK4yysa3bwBa4SuhVuWyVF65Oz56JbIpDt9pwUK-PhrVX8mn7BQM312diYcIut3pWh_ubhbKokT894CWio=s0-d "S[k+1] = max \{S[k] + A[k+1], A[k+1] \}")
(for all 
)![S[i]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tHEN8vRfmTvWDNQFrtshMnL1peKV4OiWP8eYFKuXaXzilOk4ujfmUkxkAf7Pok6gngSM5joHv2GX8NO5cQzRGznCuPH-W9UQN06bFoJRlYCsAjw4NYgtox1Ad6xzLm21XJkaM3=s0-d "S[i]")
for 
.
where ![T[i]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_s629AeIGT4tLU_THtyfXQl8S5_24lj7Z-23s0sp0lSY1SySHAAfQOGgvDJrFcFWpNJcPTFRTKUr_skp6N8o27qAkmA7FlQO6O_ttSx10ARtCBvDsgfnQZjT_Mj9RPsbdDF4J01=s0-d "T[i]")
would store the starting index for a maximum sum contiguous subsequence ending at index i. time and space.
. The key idea is this: for computing S[i] and T[i], all we need are the values of S[i-1] and T[i-1] apart from the given array A. Hence, there is no need to store all 
values of the S and T arrays. time and space.
If( leftmax < node->data && node->data < rightmin) // Means it is a BST
{
new size = rightsize+leftsize+1
update size if greater than max
return size
}
else
{
return -1;
}
Working Code:
/* Largest Binary search tree inside a binary tree -- O(n)*/
#include <stdlib.h>
#include <stdio.h>
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* insert_bst(struct node* root, int num){
if(root == NULL){
root = (struct node*)malloc(sizeof(struct node));
root->data = num;
root->left = NULL;
root->right = NULL;
return root;
}else{
if(num == root->data){
return root;
}
if(num > root->data){
root->right=insert_bst(root->right,num);
}else{
root->left=insert_bst(root->left,num);
}
}
return root;
}
void inorder_traverse(struct node* root){
if(root == NULL) return;
inorder_traverse(root->left);
printf("%d ",root->data);
inorder_traverse(root->right);
}
struct node* bst_root = NULL;
int getmaxbst(struct node* root, int& subtreemin, int &subtreemax, int& max)
{
if(root == NULL) return 0;
int leftsubtreemin = -32767, rightsubtreemin = -32767;
int leftsubtreemax = 32767, rightsubtreemax = 32767;
int x,y;
x = getmaxbst(root->left, leftsubtreemin, leftsubtreemax, max);
y = getmaxbst(root->right, rightsubtreemin, rightsubtreemax, max);
if(x==-1 || y ==-1)
return -1;
if(x==0) { leftsubtreemax = root->data; leftsubtreemin = root->data;}
if(y==0) { rightsubtreemin = root->data; rightsubtreemax = root->data;}
if(root->data < leftsubtreemax ||
root->data > rightsubtreemin){
return -1;
}
subtreemin = leftsubtreemin;
subtreemax = rightsubtreemax;
if(x+y+1 > max){
max = x+y+1;
bst_root = root;
}
return x+y+1;
}
int main()
{
struct node* root=NULL;
root=insert_bst(root,5);
root=insert_bst(root,3);
root=insert_bst(root,9);
root=insert_bst(root,7);
root=insert_bst(root,4);
root=insert_bst(root,1);
root=insert_bst(root,14);
root=insert_bst(root,11);
root->data = 0;
int a,b,c,max=-32767;
c = getmaxbst(root,a,b,max);
printf("\nmax is %d\n",max);
inorder_traverse(bst_root);
return 1;
}
TC O(N)
SC O(1)
Bus Arrival Departure
BusA 0900 hrs 0930 hrs
BusB 0915 hrs 1300 hrs
BusC 1030 hrs 1100 hrs
BusD 1045 hrs 1145 hrs
Algorithm
Its simple dynamic programming question that calculate the
number of buses at station at any time(when a bus comes or
leaves). Maximum number in that pool will be nothing but
the maximum number of buses at the bus-station at any time
,which is same as max number of platforms required.
So first sort
all the arrival(A) and departure(D) time in an int array.
Please save the corresponding arrival or departure in the
array also.Either you can use a particular bit for this
purpose or make a structure. After sorting our array will
look like this:
0900 0915 1930 1030 1045 1100 1145 1300
A A D A A D D D
Time Compelxity O(nlogn)
Space Complexity O(1)
Time Compelxity O(nlogn)
Space Complexity O(1)
