fork download
copy 
  1. #include<stdio.h>
  2. #define NEGINF -1000000000
  3. #define MAX(a,b) a>b?a:b
  4.  
  5. int a[9]={-2,1,-3,4,-1,2,1,-5,4};
  6.  
  7. int max_across(int low,int mid,int high)
  8. {
  9.     int i;
  10.     int leftsum,rightsum,sum,righti,lefti,maxsum;
  11.     leftsum=NEGINF;
  12.     sum=0;
  13.     for(i=mid;i>=low;i--)
  14.     {
  15.         sum=sum+a[i];
  16.         if(sum>leftsum)
  17.         {
  18.             leftsum=sum;
  19.             lefti=i;
  20.         }
  21.     }
  22.  
  23.     rightsum=NEGINF;
  24.     for(i=mid+1;i<=high;i++)
  25.     {
  26.         sum=sum+a[i];
  27.         if(sum>rightsum)
  28.         {
  29.             rightsum=sum;
  30.             righti=i;
  31.         }
  32.     }
  33.  
  34.     maxsum=leftsum+rightsum;
  35.     return maxsum;
  36. }
  37.  
  38. int max_sum(int low,int high)
  39. {
  40.     int left_sum,right_sum,across_sum,final_sum;
  41.     int mid=low+(high-low)/2;
  42.     if(low==high) return a[low];
  43.     left_sum=max_sum(low,mid);
  44.     printf("left_sum = %d, low = %d, high = %d\n",left_sum,low,high);
  45.     right_sum=max_sum(mid+1,high);
  46.     printf("right_sum = %d, low = %d, high = %d\n",right_sum,low,high);
  47.     across_sum=max_across(low,mid,high);
  48.     printf("across_sum = %d, low = %d, high = %d\n",across_sum,low,high);
  49.     final_sum=MAX(MAX(left_sum,right_sum),across_sum);
  50.     printf("final_sum = %d, low = %d, high = %d\n",final_sum,low,high);
  51.     return final_sum;
  52. }
  53.  
  54. int main()
  55. {
  56.     int sum;
  57.     sum=max_sum(0,9);
  58.     printf("sum = %d\n",sum);
  59.     return 0;
  60. }
Success #stdin #stdout 0s 2852KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
left_sum = -2, low = 0, high = 1
right_sum = 1, low = 0, high = 1
across_sum = -3, low = 0, high = 1
final_sum = 1, low = 0, high = 1
left_sum = 1, low = 0, high = 2
right_sum = -3, low = 0, high = 2
across_sum = -3, low = 0, high = 2
final_sum = 1, low = 0, high = 2
left_sum = 1, low = 0, high = 4
left_sum = 4, low = 3, high = 4
right_sum = -1, low = 3, high = 4
across_sum = 7, low = 3, high = 4
final_sum = 4, low = 3, high = 4
right_sum = 4, low = 0, high = 4
across_sum = -2, low = 0, high = 4
final_sum = 4, low = 0, high = 4
left_sum = 4, low = 0, high = 9
left_sum = 2, low = 5, high = 6
right_sum = 1, low = 5, high = 6
across_sum = 5, low = 5, high = 6
final_sum = 2, low = 5, high = 6
left_sum = 2, low = 5, high = 7
right_sum = -5, low = 5, high = 7
across_sum = 1, low = 5, high = 7
final_sum = 2, low = 5, high = 7
left_sum = 2, low = 5, high = 9
left_sum = 4, low = 8, high = 9
right_sum = 0, low = 8, high = 9
across_sum = 8, low = 8, high = 9
final_sum = 4, low = 8, high = 9
right_sum = 4, low = 5, high = 9
across_sum = 0, low = 5, high = 9
final_sum = 4, low = 5, high = 9
right_sum = 4, low = 0, high = 9
across_sum = 5, low = 0, high = 9
final_sum = 5, low = 0, high = 9
sum = 5
https://ideone.com/PHpxdV
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!