SHARE
TWEET

Untitled

a guest Dec 17th, 2018 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class Solution {
  2.     public int MaxSubArray(int[] nums)
  3.     {  
  4.         if(nums.Length == 1)
  5.         {
  6.             return nums[0];
  7.         }
  8.         else if(nums.Length == 0)
  9.         {
  10.             return Int32.MinValue;
  11.         }
  12.         else
  13.         {
  14.             int mid = nums.Length/2;
  15.             int Left = MaxSubArray(ArraySlice(nums, 0, mid));
  16.             int Right = MaxSubArray(ArraySlice(nums, mid+1, nums.Length));
  17.             int Cross = MaxCross(nums, mid);
  18.             if((Left > Right)&&(Left > Cross))
  19.             {
  20.                return Left;
  21.             }
  22.             else if(Right > Cross)
  23.             {
  24.                 return Right;
  25.             }
  26.             else
  27.             {
  28.                 return Cross;
  29.             }
  30.         }
  31.     }
  32.     public int[] ArraySlice(int[] nums, int start,  int end)
  33.     {
  34.         if(end < 0)
  35.         {
  36.             end = nums.Length + end;
  37.         }
  38.         int len = end - start;
  39.         int[] newArray = new int[len];
  40.         for(int i = 0; i < len; i++)
  41.         {
  42.             newArray[i] = nums[i+start];
  43.         }
  44.         return newArray;
  45.     }
  46.     public int MaxCross(int[] nums, int mid)
  47.     {
  48.         int leftSum = nums[mid];
  49.         int sum = 0;
  50.         for(int i = mid; i >= 0; i--)
  51.         {
  52.             sum += nums[i];
  53.             if(sum > leftSum)
  54.             {
  55.                 leftSum = sum;
  56.             }
  57.         }
  58.         int rightSum = 0;
  59.         sum = 0;
  60.         for(int i = mid+1; i < nums.Length; i++)
  61.         {
  62.             sum += nums[i];
  63.             if(sum > rightSum)
  64.             {
  65.                 rightSum = sum;
  66.             }
  67.         }
  68.         Console.WriteLine("Right sum is {0}", rightSum);
  69.         Console.WriteLine("Left sum is {0}", leftSum);
  70.         return leftSum + rightSum;
  71.     }
  72. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top