Instantly share code, notes, and snippets.

# sri-prasanna/MaxSubArray.cs

Created January 19, 2016 21:42
Show Gist options
• Save sri-prasanna/4b0f49942b0b03c215d3 to your computer and use it in GitHub Desktop.
Divide and Conquer solution for MaxSubArray problem.
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
 void Main() { // divide and conquer algorithm // var A = new int [] {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7}; // var A = new int [] {-3, -25, -3, -16, -23, -7, -5, 22, -4}; var A = new int [] {12, -2}; var result = new int [3]; result = FindMaxSubArray(A, 0, A.Length - 1); Console.WriteLine( result ); } // Define other methods and classes here int n = 0; int [] FindMaxSubArray(int [] A, int lo, int hi) { int mid = (int)Math.Floor((double)((lo + hi)/2)); if (lo < hi) { var lresult = FindMaxSubArray(A, lo, mid); var rresult = FindMaxSubArray(A, mid+1, hi); var midresult = FindMaxCrossing(A, lo, mid, hi); if (lresult[2] >= rresult[2] && lresult[2] >= midresult[2]) return lresult; if (rresult[2] >= lresult[2] && rresult[2] >= midresult[2]) return rresult; return midresult; } return new int [] {lo,hi,0}; } int [] FindMaxCrossing(int [] A, int lo, int mid, int hi) { Console.WriteLine(n++); int lsum = Int32.MinValue; int sum = 0; int lmax = 0; for(int i=mid; i >= lo; i--) { sum += A[i]; if (sum > lsum) { lsum = sum; lmax = i; } } int rsum = Int32.MinValue; sum = 0; int rmax = 0; for(int i=mid+1; i <= hi; i++) { sum += A[i]; if (sum > rsum) { rsum = sum; rmax = i; } } var result = new int [] {lmax, rmax, lsum + rsum}; // Console.WriteLine( result ); return result; }

### sri-prasanna commented Jan 19, 2016

Not sure if this implementation is correct, as it does not return the correct answer in case the input is `{12, -2}`. I expect it to return an array as `{12}`. But, this solution returns an array like `{12, -2}`..