Write a program to find maximum sum of subset in integer array. This is frequently asked interview question in Microsoft, Google and Amazon for position of SDE/SDET. I came up with efficient O(n) solution for this problem. If you have other solution to this problem; Please feel free to comment. Let’s dive into problem.
Problem: Write a program to find maximum sum of subset in integer array. Example: Given input: {3 2 8 9 -25 5 8 4 4 -3 5 3 -10}; The subset with the largest sum would be: {5 8 4 4 -3 5 3} So answer should be: Start: 5 End: 11 |
This is what I came up with:
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace MaxSumSubSet { class Program { static void Main(string[] args) { int[] nums = new int[] { 3, 2, 8, 9, -25, 5, 8, 4, 4, -3, 5, 3, -10 }; int start = -2; int end = -2; int max = 0; int sum = 0; for (int i = 0, j = 0; i < nums.Length; i++) { sum += nums[i]; if (sum > max) { max = sum; start = j; end = i; } else if (sum < 0) { j = i + 1; sum = 0; } } Console.WriteLine("Start:{0} End:{1}", start, end); } } } |
OUTPUT:
Start: 5 End: 11 |
December 7th, 2009 at 12:39 pm
Thank you very much for this post. I have been looking for this solution since a month.
December 7th, 2009 at 12:40 pm
It’s good to know you like our post. Keep in touch.