Maximum circular subarray sum

Given n numbers (both +ve and -ve), arranged in a circle, fnd the maximum sum of consecutive number.
Examples:

Input: a[] = {8, -8, 9, -9, 10, -11, 12}
Output: 22 (12 + 8 – 8 + 9 – 9 + 10)

Input: a[] = {10, -3, -4, 7, 6, 5, -4, -1}
Output: 23 (7 + 6 + 5 – 4 -1 + 10)

Input: a[] = {-1, 40, -14, 7, 6, 5, -4, -1}
Output: 52 (7 + 6 + 5 – 4 – 1 – 1 + 40)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] numArray = { -1, 40, -14, 7, 6, 5, -4, -1 };
            Console.WriteLine("Given array");
            Console.WriteLine("===========");
            for (int i = 0; i < numArray.Length; i++)
            {
                Console.Write(numArray[i] + " ");
            }
            Console.WriteLine("\n");
            int startIndex = 0, arrayLength = 0, maxSum = 0;
            //Starting point
            for (int i = 0; i < numArray.Length; i++)
            {
                //Sub array length
                for (int j = 1; j <= numArray.Length; j++)
                {
                    int tempSum = 0;
                    for (int k = i; k < (i + j); k++)
                    {
                        tempSum = tempSum + numArray[k % numArray.Length];
                    }
                    if (i == 0 && j == 1)
                    {
                        startIndex = i;
                        arrayLength = j;
                        maxSum = tempSum;
                    }
                    else
                    {
                        if (maxSum < tempSum)
                        {
                            startIndex = i;
                            arrayLength = j;
                            maxSum = tempSum;
                        }
                    }
                }
            }
            Console.WriteLine("Maximum circular subarray sum = " + maxSum);
            Console.WriteLine("==================================");
            for (int k = startIndex; k < startIndex + arrayLength; k++)
            {
                Console.Write(numArray[k % numArray.Length] + " ");
            }
            Console.WriteLine("\n");
        }
    }
}

Output
=======
Given array
===========
-1 40 -14 7 6 5 -4 -1

Maximum circular subarray sum = 52
==================================
7 6 5 -4 -1 -1 40

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