#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define ARRAY_SIZE 1000
int buf [ARRAY_SIZE];
int main()
{
srand((unsigned int )time(0));
int i,j,n;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)buf[i]=rand()%100-10;
for(i=1;i<=n;i++)printf("%d ",buf[i]);
printf("\n");
//creat random value of buffer and print
//max subsequence sum
long int max_sum=0;
int start=1,end,rs;
for(i=1;i<=n;i++)
{
long int this_sum=0;
start=i;
for(j=i;j<=n;j++)
{
this_sum+=buf[j];
if(this_sum>max_sum)
{
max_sum=this_sum;
rs=start;
end=j;
}
}
}
printf("rs=%d,end=%d,max_sum=%ld\n",rs,end,max_sum);//print result
}
}
//O(n*n) brute-force
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define ARRAY_SIZE 1000
int buf [ARRAY_SIZE];
long int max3(long int a,long int b,long int c)
{
return a>b?(a>c?a:c):(b>c?b:c);
}
long int max_subsequence_sum(int left,int right)
{
if(left==right)
{
if(buf[left]>0)return buf[left];
else return 0;
}
int mid=(left+right)/2;
long int max_left_sum= max_subsequence_sum(left, mid);
long int max_right_sum= max_subsequence_sum(mid+1, right);
int i,j;
long int max_leftbordersum=0,leftbordersum=0;
for(i=mid;i>=left;i--)
{
leftbordersum+=buf[i];
if(leftbordersum>max_leftbordersum) max_leftbordersum=leftbordersum;
}
long int max_rightbordersum=0,rightbordersum=0;
for(i=mid+1;i<=right;i++)
{
rightbordersum+=buf[i];
if(rightbordersum>max_rightbordersum) max_rightbordersum=rightbordersum;
}
return max3(max_left_sum,max_right_sum,max_rightbordersum+max_leftbordersum);
}
int main()
{
srand((unsigned int )time(0));
int i,j,n;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)buf[i]=rand()%100-10;
for(i=1;i<=n;i++)printf("%d ",buf[i]);
printf("\n");
//creat random value of buffer and print
//max subsequence sum
long int result=max_subsequence_sum(1,n);
printf("result=%ld\n",result);//print result
}
}
//O(nlgn)divide and conquer
//the pity is no sign of start and end of max subsequence sum
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define ARRAY_SIZE 1000
#define RANDOM_SIZE 100
int buf [ARRAY_SIZE];
int main()
{
srand((unsigned int )time(0));
int i,j,n;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)buf[i]=rand()%RANDOM_SIZE-RANDOM_SIZE/2;
for(i=1;i<=n;i++)printf("%d ",buf[i]);
printf("\n");
//creat random value of buffer and print
//max subsequence sum
long int max_sum=0;
int start=1,end,rs;
long int this_sum=0;
for(i=1;i<=n;i++)
{
this_sum+=buf[i];
if(this_sum>max_sum)
{
max_sum=this_sum;
rs=start;
end=i;
}
else
{
this_sum=0;
start=i+1;
}
}
printf("rs=%d,end=%d,max_sum=%ld\n",rs,end,max_sum);//print result
}
}
//O(n)