CODEWITHSUNDEEP
c++algorithmdata-structuresc++14
venkatesan ravi
venkatesan ravi

Reputation: 27

Which is the best algorithm to find sum of all subarray?

for example if 

a[3]={1,2,3}

 1,2,3,1+2,2+3,1+2+3

so my program should print
1
2
3
3
5
8

I know there exits a formula for calculating the total sum.
But what i want is efficient method to calculate individual sums.

A seg tree advisable?

Upvotes: 0

Views: 822

Answers (1)

Bernardo Sulzbach
Bernardo Sulzbach

Reputation: 1581

Assuming that by subarray you mean what some authors conventionally call subarray being a contiguous slice of an array, you are looking for Kadane's algorithm.

It works by incrementally finding the biggest subarray. At any given point of the search, the maximum subarray on that index is either the empty array (sum == zero) or consists of one more element than the maximum subarray that ended at the previous position. You keep track of what is the best you've ever found so you can compare subarrays with the best so far and return the actual best solution.

It may also be extended to multiple dimensions.

Upvotes: 1

Related Questions