Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Find maximum sum of sub array in O(N^3), O(N^2), O(NlogN), O(N).
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
//typedef int TYPE;
typedef long TYPE;
double print_time(struct timeval *s, struct timeval *e){
int si = (s->tv_sec%1000000)*1000+s->tv_usec/1000;
int ei = (e->tv_sec%1000000)*1000+e->tv_usec/1000;
return (double)(ei-si)/1000.0;
}
void debug(int num, TYPE* data){
if(num>100) return;
int i;
for(i=0;i<num;i++){
printf("%ld,",data[i]);
}
printf("\n");
}
void make_data(int num, TYPE* data){
//srand((unsigned)time(NULL));
srand(0);
int i;
TYPE j;
for(i=0;i<num;i++){
j=rand()%num;
if(rand()%2){
data[i]=j;
}else{
data[i]=j*(-1);
}
}
debug(num,data);
}
void func_O_N3(int num, TYPE* data){
int i,j,k,a,b;
long s=0,m=0;
for(i=0;i<num;i++){
for(j=i+1;j<num;j++){
s=0;
for(k=i;k<=j;k++){
s+=data[k];
}
if(m<s){
m=s;
a=i;
b=j;
}
}
}
printf("%d-[%ld]-%d\n",a,m,b);
}
void func_O_N2(int num, TYPE* data){
int i,j,a,b;
long s,m;
m=0;
for(i=0;i<num;i++){
s=0;
for(j=i;j<num;j++){
s+=data[j];
if(m<s){
m=s;
a=i;
b=j;
}
}
}
printf("%d-[%ld]-%d\n",a,m,b);
}
typedef struct {
TYPE s;
int a;
int b;
} _TYPE;
_TYPE max(_TYPE a, _TYPE b, _TYPE c){
if(a.s<b.s){
if(b.s<c.s) return c;
else return b;
}else{
if(a.s<c.s) return c;
else return a;
}
}
_TYPE max3(int l, int u, TYPE *data){
_TYPE t;
t.s=0;
if(l==u) return t;
int m = l+(u-l)/2;
int i,la,ub;
long s,ls=0,us=0;
s=0;
for(i=m;i>=l;i--){
s+=data[i];
if(ls<s){
ls=s;
la=i;
}
}
s=0;
for(i=m+1;i<=u;i++){
s+=data[i];
if(us<s){
us=s;
ub=i;
}
}
_TYPE a,b,c;
a.s=ls+us;
a.a=la;
a.b=ub;
b=max3(l,m,data);
c=max3(m+1,u,data);
return max(a,b,c);
}
void func_O_NlogN(int num, TYPE* data){
_TYPE a = max3(0,num,data);
printf("%d-[%ld]-%d\n",a.a,a.s,a.b);
}
void func_O_N(int num, TYPE* data){
int i,a,b;
long s,m,t;
t=s=m=0;
for(i=0;i<num;i++){
s+=data[i];
s=s>0?s:0;
if(s==0){
t=i+1;
}
if(m<s){
m=s;
a=t;
b=i;
}
}
printf("%d-[%ld]-%d\n",a,m,b);
}
int main(int argc, char* argv[]){
if(argc!=2) return 0;
int num = atoi(argv[1]);
TYPE *data = malloc(sizeof(TYPE)*num);
make_data(num,data);
struct timeval s, e;
if(num<=10000){
gettimeofday(&s,NULL);
func_O_N3(num,data);
gettimeofday(&e,NULL);
printf("func_O_N3 : %.2lf sec.\n",print_time(&s,&e));
}
if(num<=100000){
gettimeofday(&s,NULL);
func_O_N2(num,data);
gettimeofday(&e,NULL);
printf("func_O_N2 : %.2lf sec.\n",print_time(&s,&e));
}
gettimeofday(&s,NULL);
func_O_NlogN(num,data);
gettimeofday(&e,NULL);
printf("func_O_NlogN : %.2lf sec.\n",print_time(&s,&e));
gettimeofday(&s,NULL);
func_O_N(num,data);
gettimeofday(&e,NULL);
printf("func_O_N : %.2lf sec.\n",print_time(&s,&e));
return 0;
}
Owner

nishidy commented Dec 16, 2016

$ gcc -W -O3 max_sub_array.c -o max_sub_array
$ ./max_sub_array 10000
2846-[395431]-9118
func_O_N3 : 31.94 sec.
2846-[395431]-9118
func_O_N2 : 0.09 sec.
2846-[395431]-9118
func_O_NlogN : 0.00 sec.
2846-[395431]-9118
func_O_N : 0.00 sec.
$ ./max_sub_array 100000
4462-[41420970]-78116
func_O_N2 : 8.33 sec.
4462-[41420970]-78116
func_O_NlogN : 0.00 sec.
4462-[41420970]-78116
func_O_N : 0.00 sec.
$ ./max_sub_array 100000000
44987525-[806032238542]-92570498
func_O_NlogN : 4.11 sec.
44987525-[806032238542]-92570498
func_O_N : 0.27 sec.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment