   Microsoft: Youre given an array had both positive,negative integers find largest sum
  Q: You’re given an array containing both positive and negative integers and required to find the subarray with the largest sumthis is one of the typical questions which microsoft is asking...all aboutAns: It works better than posting had seen in before in this forum....Let s try it. . . A: here is given Array...  31 -41 59 26 -53 58 97 -93 -23 S: subsequent sum is palced  S[0]=A[0]; for S:   for(int i=1;i<sizeof(A);i++) {   S=S[i-1]+A;    if(S<=0) S=0; }  A: 31 -41 59 26 -53 58  97  -93  -23 S: 31  0  59 85  32 90  187  94  71   The solution is max of {S}.  so here s[6] is maximum. " Cost:  (n) time and space.Q: " First and last index (having highest sum)can be reconstructed from S. How?[Edited by - ravinder_konka on June 20, 2006 12:31:50 AM]
int BiggestSum(vector<int> vNums, int iSize){  sort(vNums.begin(), vNums.end(), greater<int>());  int iSum = 0;  for(int i = 0; i < iSize; i++)    iSum += vNums;  return(iSum);}Am I missing something?   ;  Yes - the objective is to find a subarray in the original array whose sum is the biggest possible.You seem to be ordering the array's elements, and then adding them all up. (Actually, why are you even ordering them if you're just adding the all?)   ;  Oooh, the largest subarray in the original order.  I was reading it as the largest subset of size iSize of the original array.   ;  This is a maximum subsequence problem... this algorithm is usually (PDF at link -->)taught in computer science programs when introducing the idea of dynamic programming.I just picked a link pseudo-randomly, so there may be better ones.  "Maximum subsequence algorithm" is the search term you probably want.   ;Quote:Original post by BeanDogint BiggestSum(vector<int> vNums, int iSize){  sort(vNums.begin(), vNums.end(), greater<int>());  int iSum = 0;  for(int i = 0; i < iSize; i++)    iSum += vNums;  return(iSum);}Am I missing something?LOL. Yes the part where you are required to find the substring with the largest sum of the given array. If you are going to assume the given order isnt important I can disregard the values too and replace them with what ever I want :)int* big_sum (int* array, int size, int& sub_size){  for (i=0;i<size;i++)   array=i;  sub_size = size;  return array;};Quote:Original post by BeanDogOooh, the largest subarray in the original order.  I was reading it as the largest subset of size iSize of the original array.Gotcha - I thought you were ordering them to stop adding whenever the values became negative, and had forgotten to check for that little detail :)   ;Quote:This is a maximum subsequence problem... this algorithm is usually (PDF at link -->)taught in computer science programs when introducing the idea of dynamic programming.It's strange that your link calls this a subsequence. I seem to remember a definition of subsequence more like this, which would make finding the maximum subsequence a much less interesting problem.   ;  The problem would be:Find i, j matching the following conditions:- 0 <= i <= j < array size- for any k, l such as "0 <= k <= l < array size", sum(k,l) <= sum(i,j)where sum(i, j) means the sum of elements between indices i and j inclusively.That formulation enforces that the max sub array is a contiguous part of the original array.   ;  You are looking for "Kadane's algorithm"   