Define the deficit of a subarray S to be k*size(S)-sum(S), or how much
its sum falls short of averaging k.
If the deficit of the entire array is negative, the result is the
entire array.
Otherwise, the result is the subarray created by removing the smallest
possible subarray from the front and
Define the deficit of a subarray S to be k*size(S)-sum(S), or how much
its sum falls short of averaging k.
If the deficit of the entire array is negative, the result is the
entire array.
Otherwise, the result is the subarray created by removing the smallest
possible subarray from the front and
Define the deficit of a subarray S to be k*size(S)-sum(S), or how much
its sum falls short of averaging k.
If the deficit of the entire array is negative, the result is the
entire array.
Otherwise, the result is the subarray created by removing the smallest
possible subarray from the front and
hi @all:
i am little bit confused on the discussion going here on this thread..
largest subset sum problem in computer science is NP complete as followed
http://en.wikipedia.org/wiki/Subset_sum_problem
also in book written by CLRS in chapter 35.5 i have found that The
decision problem ask whether
@ sachin : again u misunderstood the question .. question says *longest* ..
As per u'r algo ..
1. Find out start and end index of contiguous subarray which has max sum
O(n)
2.Once u have start and end index calculate avg if it satisfies the
condition then done O(n)
*NO -- even if it
@ bharat, koup
Sorry I missed this condition...
Algo can tweaked little bit further to cover all conditions..
Algorithm--
1. Find out start and end index of contiguous subarray which* has sum 0 *
O(n)
2.Once u have start and end index calculate avg if it satisfies the
condition then done O(n)
Hello,
Algorithm--
1. Find out start and end index of contiguous subarray which has max sum
O(n)
2.Once u have start and end index calculate avg if it satisfies the
condition then done O(n)
2.1 other wise run a loop through start to end index and remove trailing
elements by increasing start
Implementation
public class Kadanes {
static int maxAvgSum(int a[], float k) {
int max_so_far = 0, max_ending_here = 0, avg = 0, s = -1, e = -1, ts, te,
tsum;
boolean flag = false;
for (int i = 0; i a.length; i++) {
if (max_ending_here == 0)
s = e = i;
max_ending_here = max_ending_here +
To be correct I need the longest subarray that has an average greater than
k but my main problem here is to find the longest one. Thank you !
--
