0

C# でMax Sub Array Problemを開発しようとしています。

そして私のコードは

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 { }

時間の複雑さを最小限に抑えようとしているため、これがこのアルゴリズムを解決するための最良のアプローチであるかどうかを知りたい

ありがとうございました

4

4 に答える 4

1

O(N*logN) の複雑さでの分割統治の実現については、Introduction to Algorithms: CLRSの Chapter 4 Divide-and-Conquer 4.1 The maximum-subarray problem で説明されています。からのC# ポート。

 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
        };

    }
}
于 2013-03-15T08:13:14.997 に答える
1

コードの時間の複雑さは ですが、2 回の改修O(n^3)で改善し、 に変更できます。しかし、動的計画法によって設計されたより良いアルゴリズムまたはこれがあります。O(N^2)

このソリューションは、行列配列で解決します。注: デフォルトの最大値は、負の無限大に設定する必要があります。

これはwikiからのコードです：

配列全体が負の数で構成されている場合に、長さ 0 の部分配列が返されない問題のバリエーションは、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 ;
}
于 2013-03-15T08:25:46.983 に答える
1

ここに示されている O(N) アルゴリズムがあります: http://en.wikipedia.org/wiki/Maximum_subarray_problem

実際にはサブ配列を提供するのではなく、サブ配列の最大値のみを提供します。

入力配列には少なくとも 1 つの正の (ゼロ以外の) 数値が含まれている必要があるという重要な制限に注意してください。

範囲と最大値を返すように変更しました。

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;
        }
    }
}
于 2013-03-15T08:54:55.457 に答える
0

これを試して

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 { }
    }

参照元

于 2013-03-15T08:25:44.790 に答える