Write a function to find a largest sub-sequence in a given array of integers both positive and negative.

Examples:

{ -100, 1, 2, 3, -20, -20, -20, 2, 2, 2, 2,-100 }; Answer: 8

{ 1,2,3}; Answer: 6

{ -1,-2,-3}; Answer: -1

O(n) Solution is to use dynamic programming. You can add numbers as you walk the array in the following manner:

X[i]=X[i]+X[i-1];

So, at each step X[i] would contain the sum of all previous numbers. At this point you only need to maintain minimum and maximum numbers to get the result you need:

Examples:

{ -100, 1, 2, 3, -20, -20, -20, 2, 2, 2, 2,-100 }; Answer: 8

{ 1,2,3}; Answer: 6

{ -1,-2,-3}; Answer: -1

**Solution:**O(n) Solution is to use dynamic programming. You can add numbers as you walk the array in the following manner:

X[i]=X[i]+X[i-1];

So, at each step X[i] would contain the sum of all previous numbers. At this point you only need to maintain minimum and maximum numbers to get the result you need:

```
```

static int subArray(int[] data)

{

int max = Int32.MinValue;

int min = 0;

for (int i = 0;i < data.Length;i++)

{

if (i > 0)

data[i] += data[i - 1];

if (data[i]-min> max) max = data[i]-min;

if (data[i] < min) min = data[i];

}

return max;

}