• API
• FAQ
• Tools
• Archive
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;
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.
Not a member of Pastebin yet?