For an array of integers. Find the BIGGEST subarmake with the maximum amount

Question

Hi, I am preparing a test test for an interview, and I came across this question. I tried to try it in C #, below is my awkward answer, which I don’t even know if this is correct, but basically, I think not, could someone ask, please give me an answer so that when I rework solution, I can at least answer to verify the output. Thanks.

Sample data:

int[] arr = {5, 1, -7, 3, 7}; 

the code:

 int[] LargestsubarrayMaxSum(int[] arr) { int temp = 0; int[] resultArr = new int[arr.Length]; for (int i = 0; i < arr.Length - 1; i++) { if (i != 0) { foreach (int item in resultArr) { temp += item; } if (temp + arr[i + 1] > 0) { resultArr[i + 1] = temp + arr[i + 1]; } } else { if ((arr[i] + arr[i + 1]) >= 0) { resultArr[i] = arr[i]; resultArr[i + 1] = arr[i] + arr[i + 1]; } else { resultArr[i] = arr[i]; resultArr[i + 1] = 0; } } } return resultArr; } 

Answer 1

How about this?

 var arr = new [] {5, 1, -7, 3, 7}; var xs = from n in Enumerable.Range(0, arr.Length) from l in Enumerable.Range(1, arr.Length - n) let subseq = arr.Skip(n).Take(l) orderby subseq.Count() descending orderby subseq.Sum() descending select subseq; var maxSumSubseq = xs.First(); 

EDIT: added orderby orderby subseq.Count() descending to get the maximum length of the subsequence.

---

EDIT: added explanation as per comment.

• Select all possible starting subsequence indices:

   from n in Enumerable.Range(0, arr.Length) 

• Select all possible lengths of subsequences based on the starting index:

   from l in Enumerable.Range(1, arr.Length - n) 

• Extract the subsequence from the array:

   let subseq = arr.Skip(n).Take(l) 

• Order subsequences in descending length (i.e. the longest first) - l may be ordered instead of subseq.Count() , but the latter is more expressive, although the former is more efficient:

   orderby subseq.Count() descending 

• Calculate the sum of each subsequence and arrange the subsequences so that the highest amounts will be the first:

   orderby subseq.Sum() descending 

• Choose subsequences:

   select subseq; 

• Select only the first subsequence - this is the maximum amount with the longest length:

   xs.First(); 

Hope this helps.

Answer 2

complexity O (N) and complexity of the space O (1) . This is the best solution I know:

 #include <stdio.h> #include <limits.h> int get_max_sum(int* array, int len, int* start, int* end) { int max_sum = INT_MIN, sum = 0, i; int tmp_start = 0; for(i = 0; i != len; ++i) { sum += array[i]; // if the sum is equal, choose the one with more elements if(sum > max_sum || (sum == max_sum && (end - start) < (i - tmp_start))) { max_sum = sum; *start = tmp_start; *end = i; } if(sum < 0) { sum = 0; tmp_start = i + 1; } } return max_sum; } 

Here are some test cases:

 int main(int argc, char **argv) { int arr1[] = {5, 1, -7, 3, 7}; int arr2[] = {1}; int arr3[] = {-1, -7, -3, -7}; int arr4[] = {5, 1, -7, 2, 2, 2}; int start, end, sum; sum = get_max_sum(arr1, 5, &start, &end); printf("sum: %d, start: %d, end: %d\n", sum, start, end); sum = get_max_sum(arr2, 1, &start, &end); printf("sum: %d, start: %d, end: %d\n", sum, start, end); sum = get_max_sum(arr3, 4, &start, &end); printf("sum: %d, start: %d, end: %d\n", sum, start, end); sum = get_max_sum(arr4, 6, &start, &end); printf("sum: %d, start: %d, end: %d\n", sum, start, end); return 0; } $ ./a.out sum: 10, start: 3, end: 4 sum: 1, start: 0, end: 0 sum: -1, start: 0, end: 0 sum: 6, start: 3, end: 5 

Update1 : Added code for printing subarray index.

Update2 : If two auxiliary arrays with the same sum are found, select one element with a large number of elements.

Update3 : Fix algorithm for leading negative numbers

Answer 3

You can use the Enigmativity answer, but add an extra subseq.Count() descending order

or if you need a crazy linq request ......

 int[] arr = ....... var result = new[]{0} .Concat(arr.Select((x,i)=>new {x,i}) .Where(a=>ax<0).Select(a=>a.i+1)) .Select (i => arr.Skip(i).TakeWhile(a => a>=0)) .OrderByDescending(a=>a.Sum()) .OrderByDescending(a=>a.Count()).First(); 

However, usually you want to do this as a single cycle.

 var result=new List<int>(); var maxResult=new List<int>(); // These next four variables could be calculated on the fly // but this way prevents reiterating the list each loop. var count=0; var sum=0; var maxCount=0; var maxSum=0; foreach (var value in arr) { if (value >=0) { result.Add(value); sum+=value; count++; } else { if (sum>maxSum || (sum==maxSum && count>maxCount)) { maxSum=sum; maxCount=count; maxResult=result; } result.Clear(); count=0; sum=0; } } var returnValue=maxResult.ToArray(); 

Answer 4

  public static int[] FindMaxArrayEx(int[] srcArray) { int[] maxArray = new int[1]; int maxTotal = int.MinValue; int curIndex = 0; int tmpTotal = 0; List<int> tmpArray = new List<int>(); if (srcArray.Length != 1) { for (int i = 0; i < srcArray.Length; i++) { tmpTotal = 0; curIndex = i; tmpArray.Clear(); while (curIndex < srcArray.Length) { tmpTotal += srcArray[curIndex]; tmpArray.Add(srcArray[curIndex]); if (tmpTotal > maxTotal) { maxTotal = tmpTotal; maxArray = tmpArray.ToArray(); } curIndex++; } } } else { maxTotal = srcArray[0]; maxArray = srcArray; } Console.WriteLine("FindMaxArrayEx: {0}",maxTotal); return maxArray; } 

Answer 5

Here is a fully working solution:

 using System; using System.Collections.Generic; class MaxSumOfSubArray { static void Main() { //int[] array = { 2, 3, -6, -1, 2, -1, 6, 4, -8, 8 }; //maxSubSum(array); int digits; List<int> array = new List<int>(); Console.WriteLine("Please enter array of integer values. To exit, enter eny key different than 0..9"); while (int.TryParse(Console.ReadLine(), out digits)) { array.Add(digits); } maxSubSum(array); } public static void maxSubSum(List<int> arr) { int maxSum = 0; int currentSum = 0; int i = 0; int j = 0; int seqStart=0; int seqEnd=0; while (j < arr.Count) { currentSum = currentSum + arr[j]; if (currentSum > maxSum) { maxSum = currentSum; seqStart = i; seqEnd = j; } else if (currentSum < 0) { i = j + 1; currentSum = 0; } j++; } Console.Write("The sequence of maximal sum in given array is: {"); for (int seq = seqStart; seq <= seqEnd; seq++) { Console.Write(arr[seq] + " "); } Console.WriteLine("\b}"); Console.WriteLine("The maximum sum of subarray is: {0}", maxSum); } } 

Answer 6

  /// <summary> /// given an non-empty input array of integers, this method returns the largest contiguous sum /// </summary> /// <param name="inputArray">the non-empty input array of integeres</param> /// <returns>int, the largest contiguous sum</returns> /// <remarks>time complexity O(n)</remarks> static int GetLargestContiguousSum(int[] inputArray) { //find length of the string, if empty throw an exception if (inputArray.Length == 0) throw new ArgumentException("the input parameter cannot be an empty array"); int maxSum = 0; int currentSum = 0; maxSum = currentSum = inputArray[0]; for (int i = 1; i < inputArray.Length; i++) //skip i=0 as currentSum=inputArray[0]. { currentSum = Math.Max(currentSum + inputArray[i], inputArray[i]); maxSum = Math.Max(currentSum, maxSum); } return maxSum; } 

Answer 7

/ * - It was an algorithm that I found on the Wiki to calculate the amount, however, to get the actual subarray * I really needed to think. After spending several hours, I was able to solve this using startIndex and * endIndex int variables, and then adding the if if (max_ending_here == array [i]) {startIndex = i; } * Dang it was very difficult. I hope that you will all be reorganized, if necessary, to make some improvements. * /

 /* Initialize: max_so_far = 0 max_ending_here = 0 Loop for each element of the array (a) max_ending_here = max_ending_here + a[i] (b) if(max_ending_here < 0) max_ending_here = 0 (c) if(max_so_far < max_ending_here) max_so_far = max_ending_here return max_so_far*/ using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication3 { class Program { static void Main(string[] args) { int[] array = { -2, 1, -3, 4, -1, 2, 1, -5, 4 }; int[] largestSubArray; largestSubArray = Max_Array(array); Console.WriteLine(); Console.WriteLine("Subarray is :"); foreach (int numb in largestSubArray) Console.WriteLine(numb); Console.ReadKey(); } //Max_Array function will calculate the largest contigent array //sum and then find out startIndex and endIndex of sub array //within for loop.Using this startIndex and endIndex new subarray //is created with the name of largestSubArray and values are copied //from original array. public static int[] Max_Array(int[] array) { int[] largestSubArray; int max_so_far = 0, max_ending_here = 0, startIndex = 0, endIndex = 0; for (int i = 0, j = 0; i < array.Length; i++) { max_ending_here += array[i]; if (max_ending_here <= 0) { max_ending_here = 0; } if (max_ending_here == array[i]) { startIndex = i; } if (max_so_far < max_ending_here) { max_so_far = max_ending_here; endIndex = i; } } Console.WriteLine("Largest sum is: {0}", max_so_far); largestSubArray = new int[(endIndex - startIndex) + 1]; Array.Copy(array, startIndex, largestSubArray, 0, (endIndex - startIndex) + 1); return largestSubArray; } } } 

Exit

 Largest sum is: 6 

 'Subarray is: 4, -1, 2, 1' 

Answer 8

It is not so difficult as soon as you go to it. I thought that it was going back first, which for some reason helped.

• If all numbers are positive (or 0), the entire array will be the largest subarray with the maximum sum.
• Now we can accept this fact and apply it to positive or negative arrays and instead say that we want to include all subarrays that are positive (or 0).
• Start from the end and summarize as you move. When you find a negative number, do you think that negative number makes the rest of my sums worthless? if not, you continue ... but you also mark this point there as the current maximum amount (if it is greater than the last maximum maximum amount).
• If they are useless (i.e. the amount is now less than 0), you know that everything to the right of your index is now useless. You still keep your maximum amount in case it is the highest, though.
• start at 3 with your new index. Keep track of the indices for the current maximum amount and end.

Answer 9

A SubArray with a maximum sum in an array is an array without a minimum element element. So sort it out. and remove the minimum item. this is it. This is applicable if its only positive integer array. Otherwise, only an answer is a subarray of positive elements.

Answer 10

below code works for me:

 static void Main(string[] args) { string str = Console.ReadLine(); int [] arr = Array.ConvertAll(str.Split(' '),int.Parse); int curSum = 0, maxSum = 0; curSum = maxSum = arr[0]; for (int i = 1; i < arr.Length; i++) { curSum = Math.Max(curSum + arr[i], arr[i]); maxSum = Math.Max(curSum, maxSum); } Console.WriteLine("{0}", maxSum); Console.ReadKey(); } 

Input: -2 1 -3 4 -1 2 1 -5 4

O / P: 6