Find the subsequence with largest sum of elements in an array

user_384252 0
Viewed 43218

I recently interviewed with a company and they asked me to write an algorithm that finds the subsequence with largest sum of elements in an array. The elements in the array can be negative. Is there a O(n) solution for it? Any good solutions are very much appreciated.

c algorithm c++
9 Answers

Try the following code:

#include <stdio.h>

int main(void) {
    int arr[] = {-11,-2,3,-1,2,-9,-4,-5,-2, -3};
    int cur = arr[0] >= 0? arr[0] : 0, max = arr[0];
    int start = 0, end = 0;
    int i,j = cur == 0 ? 1 : 0;
    printf("Cur\tMax\tStart\tEnd\n");
    printf("%d\t%d\t%d\t%d\n",cur,max,start,end);
    for (i = 1; i < 10; i++) {
        cur += arr[i];
        if (cur > max) {
            max = cur;
            end = i;
            if (j > start) start = j;
        }     
        if (cur < 0) {
            cur = 0;
            j = i+1;
        }
        printf("%d\t%d\t%d\t%d\n",cur,max,start,end);
    }
    getchar();
}
user_12866840

Since, we need to find the Maximum Sub-sequence Sum, We can:

  1. Sort the Array In descending order.
  2. Take two variable sum and maxSum.
  3. Run a for loop till length n.
  4. Update maxSum when sum > maxSum.

The Java Code Snippet will be something line this:

Arrays.sort(a, Collections.reverseOrder());
int sum = 0;
for (int i = 0; i < a.length; i++) {
 sum = sum + a[i];
     if (sum > maxSum) 
         maxSum = sum;
}
System.out.println(maxSum);

Time Complexity: O(nlogn)

user_103675950
Related