How to Implement MaxSubArray in C#?

Question

I am trying to develop Max Sub Array Problem in C#

And my code is

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

I would like to know if this is the best approach to solve this algorithm as I am trying to minimize the time complexity

Thank you all for your time

It might be better to post your question on code review - http://codereview.stackexchange.com/ — Roger Rowland, Mar 15 '13 at 07:29
I don't see any advanced operations in your code.. Is there any reason why you put it in a try block? — default, Mar 15 '13 at 07:32

necrostaz · Answer 1 · 2013-03-15T10:35:32.520

Divide-and-Conquer realization with O(N*logN) complexity was described in Inroduction to Algorithms: CLRS, Chapter 4 Divide-and-Conquer 4.1 The maximum-subarray problem. C# port from.

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

    }
}

score 1 · Answer 2 · edited May 23 '17 at 10:25

time complexity of your code is O(n^3), but you can improve it with two renovations and change it to O(N^2). but there is a better algorithm or this that designed by the dynamic programming.

this solution solve it in matrix array. Note: maximum default value should be set to the infinite negative.

This is a code from the wiki:

A variation of the problem that does not allow zero-length subarrays to be returned in the case that the entire array consists of negative numbers can be solved with the following code, expressed here in C++ Programming Language.

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

thank @MatthewWatson .i attached this link into algorithm word — amin k, Mar 15 '13 at 08:57
Cool - I removed my now-redundant comment. :) Incidentally, did you notice that the value of `begin` and `end` is never used? Not really the best code to have up on Wikipedia! — Matthew Watson, Mar 15 '13 at 09:04

Matthew Watson · Answer 3 · 2013-03-15T09:00:25.540

There's an O(N) algorithm presented here: http://en.wikipedia.org/wiki/Maximum_subarray_problem

It doesn't actually give you the subarray, just the maximal value of the subarray.

Note the important restriction that the input array must contain at least one positive (nonzero) number.

I have modified it to return the range as well as the maximal value:

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

score 0 · Answer 4 · answered Mar 15 '13 at 08:25

Try this

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

Reference Source

How to Implement MaxSubArray in C#?

4 Answers4