Advertisement
teleias

largestSubsequence

Sep 17th, 2013
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.33 KB | None | 0 0
  1. public static class largestSubsequence
  2. {
  3.     public static maxSubsequence(int[] arr, int start, int end)
  4.     {
  5.         if(start == end)
  6.         {
  7.             return new obj(arr, start, end);
  8.         }
  9.         int pivot  = (end-start)/2;
  10.         obj left   = maxSubsequence(arr, start, pivot);
  11.         obj right  = maxSubsequence(arr, pivot+1, end);
  12.         obj result = new obj();
  13.         int leftBorder; int leftBorderMax; int lIndex;
  14.         for(int il = pivot; il >= 0; il--)
  15.         {
  16.             leftBorder += arr[il];
  17.             if(leftBorderMax < leftBorder)
  18.             {
  19.                 leftBorderMax = leftBorder;
  20.                 lIndex = il;
  21.             }
  22.         }
  23.         int rightBorder; int rightBorderMax; int rIndex;
  24.         for(int ir = pivot+1; ir <= end; ir++)
  25.         {
  26.             rightBorder+=arr[ir];
  27.             if(rightBorderMax < rightBorder)
  28.             {
  29.                 rightBorderMax = rightBorder;
  30.                 rIndex = ir;
  31.             }
  32.         }
  33.         if(leftBorderMax > 0)
  34.         {
  35.             result.left = lIndex;
  36.         }
  37.         if(rightBorderMax > 0)
  38.         {
  39.             result.right = rIndex;
  40.         }
  41.         return max(left, right, result);
  42.     }
  43.     public static obj max(obj a, obj b, obj c)
  44.     {
  45.        
  46.     }
  47. }
  48. public static class obj
  49. {
  50.     public int left;
  51.     public int right;
  52.     public obj(){}
  53.     public obj(int _left, int _right, int _index)
  54.     {
  55.         left = _left;
  56.         right= _right;
  57.         index= _index;
  58.     }
  59.     public static int getValue(int[] arr)
  60.     {
  61.         int result = 0;
  62.         for(int i = left; i <= right; i++)
  63.         {
  64.             result += arr[i];
  65.         }
  66.         return result;
  67.     }
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement