Created
August 28, 2018 00:56
-
-
Save jianminchen/a197c21d1f422f346bfa387e357a0b87 to your computer and use it in GitHub Desktop.
Leetcode 53 divide and conquer
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace Leetcode53_Maximum_subarray_divide_and_conquer | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
} | |
public int MaxSubArray(int[] nums) | |
{ | |
if (nums == null) | |
return 0; | |
int max = int.MinValue; | |
var result = maxStartAndMaxEnd(nums, 0, nums.Length - 1, ref max); | |
return max; | |
} | |
/// <summary> | |
/// August 27, 2018 | |
/// </summary> | |
/// <param name="nums"></param> | |
/// <param name="start"></param> | |
/// <param name="end"></param> | |
/// <param name="maxValue"></param> | |
/// <returns></returns> | |
public static int[] maxStartAndMaxEnd(int[] nums, int start, int end, ref int max) | |
{ | |
if (start == end) | |
return new int[]{nums[start], nums[end]}; | |
var middle = start + (end - start) / 2; | |
if (end - start == 1) | |
{ | |
var number0 = nums[start]; | |
var number1 = nums[end]; | |
var twoSum = number0 + number1; | |
var maxStart = Math.Max(number0, twoSum); | |
var maxEnd = Math.Max(number1, twoSum); | |
max = Math.Max(max, twoSum); | |
return new int[] { maxStart, maxEnd}; | |
} | |
var sum = 0; | |
if (middle - 1 >= start) | |
{ | |
var leftMax = maxStartAndMaxEnd(nums, start, middle - 1, ref max); | |
sum = leftMax[1]; | |
} | |
if (middle <= end) | |
{ | |
var rightMax = maxStartAndMaxEnd(nums, middle, end, ref max); | |
sum += rightMax[0]; | |
} | |
// let us consider the range include middle - 1, middle | |
max = Math.Max(max, sum); | |
return | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment