Sub array having maximum sum

Problem: Given an array of positive and negative integers, return the sub array having maximum sum.

Example: Given {1, -1, 2, 0, 1, -1}, the program should return {2, 0, 1}

 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace MaxSum

{

    class Program

    {

        static void Main(string[] args)

        {

            //Array initialization

            int[] array = { 1, -1, 2, 0, 1, -1 };

            int maxSum = 0, startIndex = 0, length = 0;

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

            {

                for (int j = 0; j <= array.Length-i; j++)

                {

                    int tempSum = 0;

                    for (int k = j; k < (j+i); k++)

                    {

                        tempSum = tempSum + array[k];

                        //Console.Write(array[k] + " ");

                    }

                    //Console.WriteLine();

                    if (i == 1 && j == 0)

                    {

                        maxSum = tempSum;

                        startIndex = j;

                        length = i;

                    }

                    else if (maxSum < tempSum)

                    {

                        maxSum = tempSum;

                        startIndex = j;

                        length = i;

                    }

                }

            }

            Console.WriteLine("Given array: ");

            //Printing the initial array

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

            {

                Console.Write(array[i] + " ");

            }

            Console.WriteLine();

            Console.WriteLine("Sub array having maximum sum: ");

            //Printing the sub array

            for (int i = startIndex; i < startIndex+length; i++)

            {

                Console.Write(array[i] + " ");

            }

            Console.WriteLine();

            Console.WriteLine("Maximum sum: " + maxSum);

        }

    }

}

 

Program Output:

================

Given array:

1 -1 2 0 1 -1

Sub array having maximum sum:

2 0 1

Maximum sum: 3

Press any key to continue . . .

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s