C# 暴力求解最大子数组

2021-02-22 11:24发布

题意:有这样一个数组:{13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };欲求得此数组的所有子数组中的,和最大的一个数组是?

例:子数组{13} > {13,-3},,,答案是:{18,20,-7,12};其和为43,

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;


namespace _2_1_1最大子数组BL

{

    /// <summary>

    /// 暴力求解最大子数组

    /// </summary>

    class Program

    {

        static void Main(string[] args)

        {

            int[] arr = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };

            int[] max = new int[16];

            int[] num = new int[16];


            for (int i = 0; i < arr.Length; i++)

            {

                for (int j = i + 1; j < arr.Length; j++)

                {

                    arr[i] += arr[j];

                    if (max[i] < arr[i])

                    {

                        max[i] = arr[i];

                        num[i] = j;

                    }

                }

            }


            for (int i = 0; i < num.Length; i++)

            {

                Console.WriteLine("最大的利润:"+max[i]+"买入日期:"+i+"卖出日期:"+(num[i]+1));

            }


            Console.ReadKey();

        }

    }

}



using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;


namespace _6_1_1最大子数组暴力求解

{

    class Program

    {



        static void Main(string[] args)

        {

            //求和最大,的子数组,

            int[] arr = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };

            int max = 0;

            int[] sum = new int[16];

            int[] numI = new int[16];

            int[] numJ = new int[16];


            for (int i = 0; i < arr.Length; i++)

            {

                max = arr[i];

                sum[i] = max;

                int temp = max;

                for (int j = i+1; j < arr.Length; j++)

                {

                    temp += arr[j];

                    if (temp > max) {

                        max = temp;

                        sum[i] = temp;

                        numI[i] = i;

                        numJ[i] = j;

                    }

                }

            }


            for (int i = 0; i < sum.Length; i++)

            {

                Console.WriteLine(sum[i] + " " + (numI[i] + 1) + " " + (numJ[i] + 1));


            }


            /* 输出最大子数组的和,和起始时间

            int maxTemp = 0;

            int maxNumI = 0;

            for (int i = 0; i < sum.Length; i++)

            {             

                if (sum[i]> maxTemp)

                {

                    maxTemp = sum[i];

                    maxNumI = i;

                }


            }

            Console.WriteLine(sum[maxNumI] + " " + (numI[maxNumI] + 1) + " " + (numJ[maxNumI] + 1));

            */

            Console.ReadKey();

        }

    }

}




作者:Czhenya

链接:https://czhenya.blog.csdn.net/article/details/80024883

来源:CSDN
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。