找到最好的情况下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.