如何在C＃中實現MaxSubArray？

Question

我想開發C＃

最大子排列問題我的代碼是

try 
     { 
      int[] Values = { 9, 1, 4, 15, -5, -41, -8, 78, 145, 14 };//Will be executed once '1' 


      int StartIndex = 0;//Will be executed once '1' 
      double Sum = 0;//Will be executed once '1' 
      double Temp = 0;//Will be executed once '1' 
      double Max = 0;//Will be executed once '1' 

      do 
      { 

       for (int i = 0; i < Values.Length; i++)//1+(N+1)+N 
       { 
        Sum = Values[StartIndex]; 

        if (StartIndex < i) 
        { 
         for (int j = StartIndex+1; j <= i; j++) 
         { 
          Sum += Values[j]; 
         } 

         if (Sum > Temp) 
         { 
          Max = Sum; 
          Temp = Sum; 
         } 
        } 
       } 
       StartIndex++; 
      } while (StartIndex<Values.Length); 


      MessageBox.Show("The Max Value is " + Max); 



     } 
     catch { } 

我想知道這是否是解決這個算法我想最好的辦法儘量減少時間複雜度

謝謝大家的時間

Answer 1

分而治之實現與O（N * logN）的複雜性被描述10，第4章分而治之4.1最大子陣問題。 C＃端口from。

class Program { 
    static void Main(string[] args) { 
     int[] values = { 9, 1, 4, 15, -5, -41, -8, 78, 145, 14 }; 
     Console.WriteLine(FindMaxSubarray(values, 0, values.Length - 1)); 
    } 

    public struct MaxSubArray { 
     public int Low; 
     public int High; 
     public int Sum; 

     public override string ToString() { 
      return String.Format("From: {0} To: {1} Sum: {2}", Low, High, Sum); 
     } 
    } 

    private static MaxSubArray FindMaxSubarray(int[] a, int low, int high) { 
     var res = new MaxSubArray { 
      Low = low, 
      High = high, 
      Sum = a[low] 
     }; 
     if (low == high) return res; 

     var mid = (low + high)/2; 
     var leftSubarray = FindMaxSubarray(a, low, mid); 
     var rightSubarray = FindMaxSubarray(a, mid + 1, high); 
     var crossingSubarray = FindMaxCrossingSubarray(a, low, mid, high); 

     if (leftSubarray.Sum >= rightSubarray.Sum && 
      leftSubarray.Sum >= crossingSubarray.Sum) 
      return leftSubarray; 
     if (rightSubarray.Sum >= leftSubarray.Sum && 
       rightSubarray.Sum >= crossingSubarray.Sum) 
      return rightSubarray; 
     return crossingSubarray; 
    } 

    private static MaxSubArray FindMaxCrossingSubarray(int[] a, int low, int mid, int high) { 
     var maxLeft = 0; 
     var maxRight = 0; 

     var leftSubarraySum = Int32.MinValue; 
     var rightSubarraySum = Int32.MinValue; 

     var sum = 0; 
     for (var i = mid; i >= low; i--) { 
      sum += a[i]; 
      if (sum <= leftSubarraySum) continue; 
      leftSubarraySum = sum; 
      maxLeft = i; 
     } 

     sum = 0; 
     for (var j = mid + 1; j <= high; j++) { 
      sum += a[j]; 
      if (sum <= rightSubarraySum) continue; 
      rightSubarraySum = sum; 
      maxRight = j; 
     } 

     return new MaxSubArray { 
      Low = maxLeft, 
      High = maxRight, 
      Sum = leftSubarraySum + rightSubarraySum 
     }; 

    } 
} 

Answer 2

試試這個

static void Main() 
    { 
     try 
     { 
      int[] Values = { 9, 1, 4, 15, -5, -41, -8, 78, 145, 14 };//Will be executed once '1' 

      int max_ending_here = 0; 
      int max_so_far = 0; 

      foreach(int x in Values) 
      { 
       max_ending_here = Math.Max(0, max_ending_here + x); 
       max_so_far = Math.Max(max_so_far, max_ending_here); 
      } 

      Console.WriteLine("The Max Value is " + max_so_far); 
      Console.ReadKey(); 
     } 
     catch { } 
    } 

Reference Source

Answer 3

代碼的時間複雜度爲O(n^3)，但你可以用兩個renovations提高它並將其更改爲O(N^2)。但有更好的algorithm或this由動態編程設計。

this解決方案在矩陣陣列中解決它。 注意：最大默認值應設置爲無限負值。

這是來自維基一個代碼：

不允許零長度的子陣列，以使整個陣列由負數可以用下面的代碼來解決的情況下，返回的問題的一種變型，這裏用C++編程語言表示。

int sequence(std::vector<int>& numbers) 
{ 
     // Initialize variables here 
     int max_so_far = numbers[0], max_ending_here = numbers[0]; 
     size_t begin = 0; 
     size_t begin_temp = 0; 
     size_t end = 0; 
     // Find sequence by looping through 
     for(size_t i = 1; i < numbers.size(); i++) 
     { 
       // calculate max_ending_here 
       if(max_ending_here < 0) 
       { 
         max_ending_here = numbers[i]; 
         begin_temp = i; 
       } 
       else 
       { 
         max_ending_here += numbers[i]; 
       } 
       // calculate max_so_far 
       if(max_ending_here > max_so_far) 
       { 
         max_so_far = max_ending_here; 
         begin = begin_temp; 
         end = i; 
       } 
     } 
     return max_so_far ; 
} 

Answer 4

有一個O這裏介紹（N）算法：http://en.wikipedia.org/wiki/Maximum_subarray_problem

實際上它並不會給你的子陣，只是子數組的最大值。

注意，輸入數組必須包含至少一個正（非零）號的重要限制。

我已經修改了它返回的範圍以及最大值：

using System; 

namespace Demo 
{ 
    public static class Program 
    { 
     public static void Main(string[] args) 
     { 
      //int[] numbers = new[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 }; 
      //int[] numbers = new[] { 1, 1, 1, 1, 1, 1, 1, 1 }; 

      int[] numbers = new[] {9, 1, 4, 15, -5, -41, -8, 78, 145, 14}; 

      var result = FindMaximumSubarray(numbers); 

      Console.WriteLine("Range = {0}..{1}, Value = {2}", result.StartIndex, result.EndIndex, result.Value); 
     } 

     public static MaximumSubarray FindMaximumSubarray(int[] numbers) 
     { 
      int maxSoFar = numbers[0]; 
      int maxEndingHere = numbers[0]; 
      int begin = 0; 
      int startIndex = 0; 
      int endIndex = 0; 

      for (int i = 1; i < numbers.Length; ++i) 
      { 
       if (maxEndingHere < 0) 
       { 
        maxEndingHere = numbers[i]; 
        begin = i; 
       } 
       else 
       { 
        maxEndingHere += numbers[i]; 
       } 

       if (maxEndingHere > maxSoFar) 
       { 
        startIndex = begin; 
        endIndex = i; 
        maxSoFar = maxEndingHere; 
       } 
      } 

      return new MaximumSubarray 
      { 
       StartIndex = startIndex, 
       EndIndex = endIndex, 
       Value = maxSoFar 
      }; 
     } 

     public struct MaximumSubarray 
     { 
      public int StartIndex; 
      public int EndIndex; 
      public int Value; 
     } 
    } 
}