查找最佳案例方案C#

Question

我有以下问题要解决，但我不确定该如何解决：

停车场彼此相邻，它们的位置类似于一条直线。每个停车场都有分配给它的价值(利润)。您可以购买任意数量的批次，但它们必须彼此相邻(在一个连续的集合中)。

输入(这是给定的/您要键入的内容)：

批次数:9

每个停车场的值:即-5，0，7，-6，4，3，-5，0，2

表示(为了更容易查看)每个框包含每个批次的利润：

​

​

输出:应为:3 6 8含义: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. 为最大子集的和创建了一个sum变量。这将保存我们答案的总和。8在你的例子中。
3. 做了另一组first/last/sum变量，我们将在停车位的开头作为我们的“当前”variables.
4. Start。将当前的第一个变量和当前的最后一个变量放在开始处，并更新和。
5. 现在，您将通过移动当前的最后一个变量并更新和，来循环遍历每个停车位。
6. 如果当前和大于最大迄今和，则在当前和为负或变为零的任何时刻，将所有当前变量保存到最大迄今和中，我们的子集不再帮助我们获得最大值，因此通过将当前第一个移到当前最后一个位置并重置当前和为零来重新启动它。
7. 一旦我们到达终点，返回最大迄今变量

Answer 2

这里有一个提示，可以让算法更有效:看看每一端的总和是如何加起来的。例如，根据您提供的内容，从左侧开始，总数将是-5，-5，2，-4，0，3，-2，-2，0，0，从右侧开始，它们将是2，2，-3，0，4，-2，5，5，0。