找到最好的情況下C＃

Question

我有以下的解決，我不知道如何處理這樣的：

有停車場是彼此相鄰和它們的位置酷似一條直線。每個停車場都有一個值（利潤）分配給它。您可以根據需要購買儘可能多的批次，但它們必須彼此相鄰（在一組連續的集合中）。

INPUT（這是所給/你會類型）：

數量很多：9

值對於每個停車場：即：-5，0，7，-6，4， 3，-5，0，2

表示（爲了容易觀看） 每個盒子包含每個大量的利潤：

OUTPUT： 應該是：含義： 3 - 開始批次＃， 6 - 結束批號， 8 - 利潤總額（7 - 6 + 4 + 3）

如果有一個以上的答案，程序應該寫出包含最少停車位數量的程序。如果還有不止一個可能的答案，你的程序可以寫任何一個答案。

請幫助。提前致謝。

編輯： 我得到它的工作：

/// <summary> 
    /// The problem 2. 
    /// </summary> 
    public class MySuperAwesomeClass 
    { 
     #region Constants and Fields 

     /// <summary> 
     /// The seq end. 
     /// </summary> 
     private static int seqEnd = -1; 

     /// <summary> 
     /// The seq start. 
     /// </summary> 
     private static int seqStart; 

     #endregion 

     // Quadratic maximum contiguous subsequence sum algorithm. 
     #region Public Methods and Operators 

     /// <summary> 
     /// The max sub sum 2. 
     /// </summary> 
     /// <param name="a"> 
     /// The a. 
     /// </param> 
     /// <returns> 
     /// The max sub sum 2. 
     /// </returns> 
     public static int maxSumSub(int[] a) 
     { 
      int maxSum = 0; 

      for (int i = 0; i < a.Length; i++) 
      { 
       int thisSum = 0; 
       for (int j = i; j < a.Length; j++) 
       { 
        thisSum += a[j]; 

        if (thisSum > maxSum) 
        { 
         maxSum = thisSum; 
         seqStart = i; 
         seqEnd = j; 
        } 
       } 
      } 

      return maxSum; 
     } 

     #endregion 

     #region Methods 

     /// <summary> 
     /// The main. 
     /// </summary> 
     private static void Main() 
     { 
      Console.WriteLine("Enter N:"); 
      string stringInput = Console.ReadLine(); 
      int[] a = new int[Convert.ToInt16(stringInput)]; 

      Console.WriteLine("Enter profit values:"); 
      for (int i = 0; i < Convert.ToInt16(stringInput); i++) 
      { 
       string value = Console.ReadLine(); 
       a[i] = Convert.ToInt16(value); 
      } 

      int maxSum = maxSumSub(a); 
      Console.WriteLine(string.Format("{0} {1} {2}", seqStart, seqEnd, maxSum)); 
      Console.ReadKey(); 
     } 

     #endregion 
    } 

除了我想不通這部分： 如果有一個以上的答案，程序應該編寫一個包含停車次數最少的一個手。

Answer 1

這是經典的最大子集總和問題。沒有代碼，因爲這是家庭作業，但這裏是一般的解決方案。如果你仍然陷入困境，我相信你可以通過搜索標題在線查找代碼。

1. 爲最大子集創建第一個/最後一個索引變量。這些將舉行我們的答案的停車位。在你的例子中分別是3和6。
2. 爲最大子集的總和做一個總和變量。這將持有我們答案的總和。 8在你的例子中。
3. 創建另一組第一/最後/總和變量，我們將成爲我們的「當前」變量。
4. 從停車位開始。在開始時放置當前的第一個和當前的最後一個變量並更新總和。
5. 現在，您將通過移動當前最後一個變量並更新總和來遍歷每個停車位。
6. 如果當前總和大於最大總和，則將所有當前變量保存到最大爲止的變量中。
7. 如果在任何時候我們的當前總和下降到負值或變爲零，我們的子集並沒有幫助我們獲得最大值，所以通過將電流先移到最後一個位置並將當前總和重置爲零來重新啓動它。
8. 一旦我們到達終點返回最大那麼遠變量

Answer 2

這裏有一個提示的方式可以使算法更有效：看從兩端總計如何積少成多。例如，根據您提供的內容，從左側開始，總數爲-5，-5，2，-4，0，3，-2，-2，0，從右側開始，它們將是2,2 ，-3，0，4，-2，5，5，0.