You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum.

EXAMPLE

input: {2, -8, 3, -2, 4, -10}

output: 5 [ eg, {3, -2, 4} ]

EXAMPLE

input: {2, -8, 3, -2, 4, -10}

output: 5 [ eg, {3, -2, 4} ]

Answer :

You might have identified that dynamic programming is appropriate for this problem. Let’s write down the recurrence:

sum(i,j) = max_k sum(i,k) + sum(k+1, j)

This will give an O(N^3) solution. A brute force summing of the sequences will give the same time.

A simple linear algorithm will work by keep track of the current subsequence sum. If that sum ever drops below zero, that subsequence will not contribute to the subsequent maximal subsequence since it would reduce it by adding the negative sum.

You might have identified that dynamic programming is appropriate for this problem. Let’s write down the recurrence:

sum(i,j) = max_k sum(i,k) + sum(k+1, j)

This will give an O(N^3) solution. A brute force summing of the sequences will give the same time.

A simple linear algorithm will work by keep track of the current subsequence sum. If that sum ever drops below zero, that subsequence will not contribute to the subsequent maximal subsequence since it would reduce it by adding the negative sum.

public class SumArr { public static void main(String[] args) { int a[] = {6,-8, 3, -2, 4}; int maxsum = 0; int sum = 0; for (int i = 0; i < a.length; i++) { sum += a[i]; if (maxsum < sum) { maxsum = sum; } else if (sum < 0) { sum = 0; } } System.out.println(maxsum); } }

Click For Answer

Assume we have an exhibit like {4, - 5, 6} – then could "6" be viewed as the most noteworthy consistent grouping. We will accept that yes it can be – in spite of the fact that you may need to illuminate with you're questioner if posed this question in a meeting situation. He/she may not consider only one worth in the exhibit to be an adequate answer, in which case the answer above would be 4 + - 5 + 6, which is 5. In any case, make sure to elucidate what your questioner needs since that shows scrupulousness – which is a quality each business needs .

ReplyDeletewrite my paper for cheap .