Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 6th, 2012  |  syntax: C++  |  size: 1.66 KB  |  hits: 16  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4. int * find_max_crossing(int * v,int left,int mid,int right)
  5. {
  6.     int max_left  = v[mid],
  7.         max_right = v[mid+1],
  8.         cr_left   = v[mid],
  9.         cr_right  = v[mid+1];
  10.     int * array = new int[3];
  11.     array[0] = mid;array[1] = mid+1;
  12.     for(int i = mid-1;i>=left;i--)
  13.     {
  14.         cr_left+=v[i];
  15.         if(cr_left > max_left)
  16.         {
  17.             max_left = cr_left;
  18.             array[0] = i;
  19.         }
  20.     }
  21.     for(int i = mid+2;i<=right;i++)
  22.     {
  23.         cr_right+=v[i];
  24.         if(cr_right > max_right)
  25.         {
  26.             max_right = cr_right;
  27.             array[1] = i;
  28.         }
  29.     }
  30.     array[2] = max_right + max_left;
  31.     return array;
  32. }
  33. int * find_max_subarray(int * v,int left,int right)
  34. {
  35.     if(left == right)
  36.     {
  37.         int * array = new int [3];
  38.         array[0] = array[1] = left;
  39.         array[2] = v[left];
  40.         return array;
  41.     }
  42.     else
  43.     {
  44.         int mid = (left+right)/2;
  45.         int * crossing = find_max_crossing(v,left,mid,right);
  46.         int * left = find_max_subarray(v,left,mid);
  47.         int * right = find_max_subarray(v,mid+1,right);
  48.         if(crossing[3] > left[3] && crossing[3] > right[3])
  49.         return crossing;
  50.         if(left[3] > crossing[3] && left[3] > right[3])
  51.         return left;
  52.         return right;
  53.     }
  54. }
  55. int main()
  56. {
  57.     ifstream in("ssm.in");
  58.     ofstream out("ssm.out");
  59.     int pos1,pos2,n;
  60.     in >> n;
  61.     int * v = new int[n];
  62.     for(int i = 0;i<n;i++)
  63.     in >> v[i];
  64.     int * res = find_max_subarray(v,0,n-1);
  65.     cout << res[2] << " " << res[1] << " " << res[0];
  66.     return 0;
  67. }
create a new version of this paste RAW Paste Data