Write a function max_sum that takes v a row vector of numbers & n,a positive integer as inputs.The function needs to find n consecutive elements of v whose sum is largest possible.It returns summa & index of first element of n consecutive integers.

%Example-[summa,index]=max_sum([1 2 3 4 5 4 3 2 1],3)
% summa=13
% index=4
function [summa,index]=max_sum(v,n)
total=v(1,1);
if n>v
summa=0;
index=-1;
else
for ii=1:length(v)
jj=ii+(n-1);
if jj<=length(v);
total=[total,sum(v(ii):v(jj))];
end
[summa,index]=max(total);
end
end

12 Comments

% total=[total,sum(v(ii):v(jj))]; this is not correct
% total=[total,sum(v(ii:jj))]; this is correct
%[summa,index]=max(total); this is not correct
[summa,index]=max(total(2:end)); %this is correct
can someone help me??
that's my cod for the same qust. when they come to the randoum vectors (dosenot accept)
i took care about the sign and also there is problem
why!!!
function [summa,index]=max_sum(v,n)
if n>length(v)
summa=0;
index=-1;
return
end
ii=v;
w=[];
p=[];
for i =1:n
[w(i),p(i)]=max(v);
v(p(i))=-1e9;
end
summa=sum(w);
index=ii(min(p));
end
Why do you expect your algorithm to work? I don't understand what you're doing here. It seems -1e9 is supposed to function as -inf, but I don't understand why you're doing what you're doing. Every function needs documentation, yours is lacking it.
@nigar shaik could you explain me [summa,index]=max(total(2:end)); %this is correct this statement and this statement force to add the largest element when we mention the index 3 is it because of 'max' function. Whats is the technique behind ii+(n-1)? explain me please
this is not correct
% if n>v
this is correct
% if n>length(v)
Why is the function (2:end)? What exactly is it pointing to?
Could you be more specific about wo is using (2:end) ? I looked through a number of postings here, but I did not notice anyone using 2:end ?
so @nigar shaik had mentioned this answer in their post, but when I tried to input the answer into the lab I was sure what it meant exactly.
would you please explain the line : total=v(1,1); and total=[total,sum(v(ii):v(jj))];
function [summa,index]=max_sum(v,n)
summa=1;
c=size(v,2);
p=0;
if(n<=c)
for jj=1:(c-n+1)
s=0;
for ii=jj:jj+n-1
s=s+v(1,ii);
end
p = v(1,jj);
if(s>summa)
summa=s;
index=p;
end
end
else
summa = 0;
index =-1;
end
end

 Accepted Answer

v = [1 2 3 4 5 4 3 2 1] ;
n = 3 ;
N = length(v) ;
sumn = zeros(1, N - n + 1); % Pre-allocation
for i = 1:N - n + 1
sumn(i) = sum(v(i:(i+n-1))) ;
end
[val,idx] = max(sumn)

22 Comments

Can you please explain the pre-allocation step??Why is it necessary here??why the row vector is till N-n+1 here??
preallocation makes the code more efficient. When you do not preallocate, MATLAB has to take a copy of the current content every time you extend the array.
Suppose the vector length is 6 and the window size is 3. The first window is 1, 2, 3. The second window is 2, 3, 4. The third window is 3, 4, 5. The fourth window is 4, 5, 6. That is a total of 4 windows, which is 6-3+1.
My code is working well even without preallocation! @ Walter Roberson
function [summa,index]=max_sum(v,n)
if n>length(v)
summa=0;
index=-1;
else
for ii=1:length(v)
jj=ii+(n-1);
if jj<=length(v);
summa(ii)=sum(v(ii:jj));
end
end
[summa,index]=max(summa);
end
end
Now give it a gigabyte array and time that compared to the version with preallocation.
Ohh..Now I get it...preallocation is done to save the execution time especially for longer arrays...
yes, preallocation can make a huge difference in execution time.
If you reset a variable to 0, it makes more sense to do that just before the loop.
Your mistake is in thinking the minimum for a sum 0. It is not, the lowest value a sum can have is -inf.
Hey, i still don't understand what is the meaning of i+n-1 ?
Essentially the goal is to add n numbers starting from the index i. To get that you need 0:(n-1) and add it to i. One way to do that is to simply add i to both sides of the colon: i:(i+n-1).
hello, please i did not understand, what is b and c? why are we using them?
b is the current sum that is being built up. c is the best sum found so far.
What would be your guess? Look at which values are selected from v inside the loop.
i am having an error (undefined function 'max_sum for input arguments of type double)
Please help me to find out what is going on here. I am keeping getting the same incorrect output.
If you run this in Matlab you can use breakpoints to run your code line by line. That will show you at least what is going wrong with the case of an empty input.
There is a possibility that there is more than one location that is the maximum. The find() step returns all of the locations and min() of the find returns the first. Another way of doing that would be to use find(Summa==S, 1)

More Answers (23)

function [summa, index] = max_sum(v,n)
L = length(v);
S=zeros(1,L-n+1);
if n > L
summa = 0;
index = -1;
return
else
for i = 1:(L-n+1)
S(i)=sum(v(i:(i+n-1)));
end
summa = max(S);
ind = find(S == summa);
index = min(ind);
end
end

6 Comments

function [summa,index]=max_sum(v,n)
z=0;
if n > length(v)
summa=0;
index= -1;
return
else
for ii=1:(length(v)-n+1)
jj=ii+(n-1);
if jj <= length(v)
w=sum(v(ii:jj));
z(ii)=w;
end
end
end
summa=max(z);
b=find(summa==z);
index=min(b);
end
Can somebody help me explain this part of the code :
ind = find(S == summa);
index = min(ind);
Cheers,
The first line returns the linear indices of S where S==summa.
The second line returns the minimum of those indices.
Both lines are unnecessary, because max() will return that index if you actually request it. Why do all this:
summa = max(S);
ind = find(S == summa);
index = min(ind);
... when you can just do:
[summa index] = max(S);
You can get a speedup by using a convolution to calculate the moving sum:
v=randi(100,2000,1);
n=10;
clc
timeit(@() option1(v,n))
ans = 3.4287e-04
timeit(@() option2(v,n))
ans = 3.5765e-05
function [val,idx]=option1(v,n) % function as suggested by KSSV
if n>numel(v),val=0;idx=-1;return,end %my addition
N = length(v) ;
sumn = zeros(1, N - n + 1); % Pre-allocation
for i = 1:(N - n + 1)
sumn(i) = sum(v(i:(i+n-1))) ;
end
[val,idx] = max(sumn);
end
function [val,idx]=option2(v,n)
if n>numel(v),val=0;idx=-1;return,end
sumn=conv(v,ones(n,1),'valid');
[val,idx] = max(sumn);
end

1 Comment

Edited only to demo the code.
An order of magnitude improvement and it's nice and concise -- what's not to like?
N=3;
v = [1 2 3 4 5 4 3 2 1];
[s,index] = maxsum(v, N)
Using this function
%% NOTE this function returns empty outputs if N>length(v)
% might be more sensitive to numerical error
function [s,index] = maxsum(v, N);
c=cumsum([0; v(:)]);
[s,index]=max(c(N+1:end)-c(1:end-N));
end
Result
s =
13
index =
4
>>

4 Comments

Nice thinking to implement the moving max this way.
There is something strange going on with the performance relative to my answer. There are some sharp jumps around k=[2050 8200 89000]. I have no idea why this is.
k_list=linspace(10,100000,500);
rng(1)%equalize between runs
[t1,t2]=myfun(k_list);
rat1=t2./t1;
rat2=movmean(rat1,3);
figure(1),clf(1)
subplot(1,2,1),drawnow
plot(k_list,rat1,'.b',k_list,rat2,'r')
legend({'maxsum/conv','smoothed'})
subplot(1,2,2),drawnow
plot(k_list,t1,'b',k_list,t2,'r')
legend({'conv','maxsum'})
function varargout=myfun(k)
varargout=cell(1,nargout);
if numel(k)>1,[varargout{:}]=arrayfun(@myfun,k);return;end
v=randi(100,round(k),1);n=10;
t1=timeit(@() option2(v,n));
t2=timeit(@() maxsum(v,n));
if nargout==1,varargout{1}=t2/t1;
else,varargout={t1,t2};
end
end
function [val,idx]=option2(v,n) %corrected as suggested by Bruno
%k=[ones(n,1);zeros(n-1,1)];%convolution kernels are flipped before moving them over the target array
%sumn=conv(v,k,'same');
if n>numel(v),val=0;idx=-1;return,end
sumn=conv(v,ones(n,1),'valid');
[val,idx] = max(sumn);
end
function [s,index] = maxsum(v, N)
c=cumsum([0; v(:)]);
[s,index]=max(c(N+1:end)-c(1:end-N));
end
@Rik: I have not read the timing yet, but not sure I understand the convolution code
v=-ones(5,1)
[val,idx]=option2(v,2)
I get
v =
-1
-1
-1
-1
-1
val =
-1
idx =
5
>>
Is that your intention?
The output val should be -2 as we sum two "-1" regardless where the window is.
I think you should use 'valid' options in CONV and not padding any zero in the kernel. Should workouk carefully to the index of max for N odd/even.
Thanks for the correction. I tested it for random lengths random vectors with random N against your code, and it seems to match now.
The fix doesn't affect the timing.
The faster timing of CONV for large array can be perhaps explained by multi-thread of the engine, that cannot be carrierd out with CUMSUM, which is sequential calculation.
TMW comes from far, the CONV in the earlier years suffered from performance. Now they have improved it greatly.
In any case a factor of 0.7 1.5 between two methods are to me essentially ... 1.
In any case your code get a vote from me.
function [s,index] = maxmovsum(v, N)
c = movsum(v,N);
[s,index] = max(c(1+floor(N/2):end-floor((N-1)/2)));
end
function [summa, ind] = max_sum(v,n)
% If n is greater than v return the specified values
% Using return keyword exits the function so no further code is
% evaluated
if n > length(v)
summa = 0;
ind = -1;
return;
end
% Initialize summa to -inf.
% Then work through the vector, checking if each sum is larger than the
% current value of summa
summa = -inf;
ind = -1;
% Once we get to length(v)-n+1 we stop moving through the vector
for ii = 1:length(v)-n+1
currentV = v(ii:(ii+n-1));
currentSumma = sum(currentV);
% If currentSumma greater than summa, update summa and ind
if currentSumma > summa
summa = currentSumma;
ind = ii;
end
end
end

3 Comments

Your code is indeed well-commented, but what does it add to this thread?
Could you explain the summa = -inf; line ?
Is -inf a built in keyword or something ?
inf is the keyword for infinity. Negative infinity is guaranteed to be the lowest value possible.
function [summa,index] = max_sum(v,n)
l=length(v);m=0;t=0;pointer=1;index=0;
%When n is larger than the length of vector v
if n>l
summa=0;
index=-1;
else
%When n is smaller than the length of vector
for a = 1:n
m=m+v(a);
end
for i = 1:(l-(n-1))
k=i;t=0;
for j = 1:n
t = t+v(k);
k=k+1;
end
if t>m
m=t;
pointer=i;
end
end
summa=m;
index=pointer;
end
I have written this code without using any inbuilt functions, just using loops. It works great!
I know it looks kinda ugly, can anyone help me optimize this code and make it shorter?

1 Comment

Have you looked at the other solutions in this thread?
Also, you already used a builtin function on your first line: length.
% Here is the working code for This Problem statement
function [summa index] = max_sum(v,n)
ii = 1;
jj = n;
% Initialize summa to zero
summa = 0;
% if n is greater than number of elements in v the return summa = 0, index = -1
if n>numel(v)
summa = 0;
index = -1;
% pro tip
% If n is equal to number of elements in v then index will always be 1 and summa = sum(v(ii:jj))
elseif n==numel(v)
summa = sum(v(ii:jj));
index = 1;
else
% while loop for calculating the sum of n elements of subsequence of v
while jj<=numel(v)
% If sum of n elements of subsequence of v is greater than the previous one
% then that sum is stored in summa and index of first element is stored in index
if sum(v(ii:jj))>summa
summa = sum(v(ii:jj));
index = ii;
end
if sum(v(ii:jj))<0 && summa == 0
summa = sum(v(ii:jj));
index = ii;
end
ii = ii + 1;
jj = jj + 1;
end
end
and this is my solution for it:
function [summa, index] = max_sum(v, n)
%creat an empty vector for cunsecutive sums, and ultimately determine the
%highest value and its index with max(w)
w = [];
ii = 1;
if n > length(v)
summa = 0
index = -1
return;
else
while n <= length (v)
w(ii) = sum(v(ii:n));
ii = ii + 1;
n = n + 1;
end
[summa, index] = max(w)
end
%I have checked, it works :)
I came up with a function that, I think, accomplishes this task. It runs fine in my MATLAB (2020a). However, it doesn't seem to be acceptable in the Assignment Submission. Anyone know why this could be the case?
function[summa,index]=max_sum(v,n)
if n>length(v)
index=-1;
summa=0;
else
sumn=movsum(v,n);
[summa,index]=max(sumn);
index=index-1;
end
end

5 Comments

sum(n) is sum() of a scalar, which will give you the same scalar in return, and max() of that scalar is always going to be the scalar again.
Question: why do you compute sumn if you are not going to use it?
@Walter thanks for the reply. I misstyped- just fixed sum(n) to what my actual code is, which is max(sumn). Thus, I am trying to let it use logical indexing to find the max and its location. It does work for various examples in my testing.
Sorry, not logical indexing. That would be "normal" indexing, right? [summa,index]=max(sumn) gives the maximum and index of that (middle) value in the vector sumn. The next line changes that index to the first value in that rolling sum. When running the code with my debugger, it seems to work with a range of values.
@Eric, Actually when we type for example [summa,index] = max(sum); it gives the maximum value which is passed to summa, but in index it passes the index of the first no.
[Y,I] = max(X) returns the indices of the maximum values in vector I.
If the values along the first non-singleton dimension contain more
than one maximal element, the index of the first one is returned.
%why second problem doesn't run?
function [summa,index] = max_sum(v,n)
s = size(v); b = 0; c = 0; index = 0;
if s(2) < n
index = s(2) - n;
summa = 0;
return
end
for i = 1:s(2)-n+1
c = sum(v(i:i+n-1));
if c > b
b = c;
index = i;
else
b = b;
end
end
summa = b;
end
%Variable ind has an incorrect value.
% max_sum([ -66 31 61 60 -70 7 9 0 8 90 -54 72 12 ...
% 89 -50 4 86 -3 83 -52 ], 23) returned sum = 0 and index = -3 which is incorrect...

3 Comments

Have you stepped through your code with the debugger?
in my matlab program,, it returns
summa =0
index = -3
with upper problem.
I'm not sure which part is not solved.
Did I not understand the problem?
Put a breakpoint on the first line. Then use the debugger to execute your function line by line. When do you see the index go negative? When do your variable get unexpected values?
When you do that you will notice that your assumption of a column vector input isn't enforced anywhere.
function [m k]=max_sum(v,n)
m=0;
if n>length(v)
k=-1;
m=0;
return
else
for k=1:((length(v)-n)+1);
while m<max(sum(v(k:((n-1)+k))));
m=max(sum(v(k:((n-1)+k))));
m=m;
k=k;
end
end
end

2 Comments

Can you guys help me check for this,
I try several time inserting the break statement in the loop but the iteration still continues, it is suppose to stop at k=4 when my input argument is ([1 2 3 4 5 4 3 2 1],3)
m=m; and k=k; will not do anything, so why are they in your code? Also, you posted this as an answer, but it is a question. (and you forgot to format your code as code)
Are you aware that break will only stop one loop, not all? And have you looked at the other solutions in this thread?
function [summa, index] = max_sum(v,n)
summa = 0;
i = 0;
j = v;
m = [];
c = 1;
if n>v
summa=0;
index=-1;
else
while i < n
c = numel(v(v==max(j))); % number of times the element is in the array
summa = summa + max(j)*c; % multiplying by c
b = find(v==max(j)); % find the max elemnets of v
m = [m b];% array of positions with max element
j = j(j<max(j));% remove the max number from array
i = i + 1;
end
t = sort(m);
index = t(1,1)
end
% I am not able to stop i from goigng to value 3 which gives the error for sum and index
% tbh, I used some help from these forum answers too
function [summa,index]=max_sum(v,n)
% first checking whether the size of row vector v is less than n or not
% if yes then print according to the given statement
if n>length(v);
summa=0;
index=-1;
else
% so you are thinking about why i took (-n+1) right?
% think of a value of size of row vector v and n
% you will get to know the answer by yourself ,example take size of v= 10 & n=10
for i=1:(length(v)-n+1);
mysum(i)=sum(v(i:i+n-1));
end
summa=max(mysum);
% I couldn't find this one, hence i used the help of this forum
x=find(mysum==summa);
index=min(x);
end
%i dont know what to do. my works pretty good with positive integers. I dont know wht it has errors with negative integers
function [summa, index] = max_sum(v,n)
summa = 0;
ii = 1;
jj = n;
total = [];
if n > numel(v)
summa = 0;
index = -1;
elseif n == numel(v)
summa = sum(v(ii:jj));
index = v(1,1);
elseif n < numel(v)
for ii = 1:numel(v)
jj = ii + (n - 1);
if jj <= numel(v);
total = [total, sum(v(ii:jj))];
end
end
summa = max(total);
x = find(total == summa);
index2 = min(x);
index = v(index2);
end

3 Comments

index = v(1,1);
The value returned for index should not be the content of v, it should be the location in v.
total = [total, sum(v(ii:jj))];
You need to store the ii value as well because you need to return an index into v, not an index into total.
Thanks for the heads up. I already have the answer. This code works fine now.
function [summa, index] = max_sum(v,n)
summa = 0;
ii = 1;
jj = n;
total = [];
if n > numel(v)
summa = 0;
index = -1;
elseif n == numel(v)
summa = sum(v(ii:jj));
index = 1;
elseif n < numel(v)
for ii = 1:numel(v)
jj = ii + (n - 1);
if jj <= numel(v);
total = [total, sum(v(ii:jj))];
end
end
summa = max(total);
x = find(total == summa);
index = min(x);
end
it worked for me thank you
i.e the reply above me
function [a,b]=max_sum(A,B)
n=1;
C=0;
for ii = 1:(size(A,2)-B+1)
C(n)=sum(A(n:(B+n-1)));
n=n+1;
end
if B>size(A,2)
a=0;
b=-1;
else
a=max(C);
b=find(C==max(C));
end
I don't get what is variable ind, and how's sum 4 index9 wrong; can someone pls help? Thanks!

2 Comments

What happens when you try this input to your function?
[a,b]=max_sum([1 2 3 4 5 4 3 2 1],2)
a = 9
b = 1×2
4 5
Is that correct? How can the index (the second output) be multiple values?
function [a,b]=max_sum(A,B)
n=1;
C=0;
for ii = 1:(size(A,2)-B+1)
C(n)=sum(A(n:(B+n-1)));
n=n+1;
end
if B>size(A,2)
a=0;
b=-1;
else
a=max(C);
b=find(C==max(C));
end
end
This is my answer
function [summa,index] = max_sum(v,n)
b=1;
summa = -1000000;
%i start it with -1000000 because you ALWAYS want to overwrite your summa
index = 0;
if n > size(v)
summa = 0;
index = -1;
return
else
%this if checks for size condition if n is bigger than the size summa is 0
%and index -1
while n<=length(v);
%this will break when n = to lenght of the vector
if sum(v(b:n)) > summa
%this condition sets the sumatory of the position from b to n.
%In this case b starts in 1 and n is the input, if the sum is
%bigger than the summa it overwrites it, thats why we wanted
%always to overwrite the value summa and we started it with
%-1000000
summa = sum(v(b:n));
index = b;
end
b = b+1;
n = n+1;
%adds +1 to b and n so my positions go from 1:n to 2:n+1 to 3:n+2
%till n = the lenght and it stops
end
end

3 Comments

the variable double has a max min number, idc wich is it. But u can change the -1000000 for that max min number that the memory can hold in the variable if u want. that should solve it. if ur input is that max min number u can add a counter of times the summa it equal to the starting number, save that position and return that position
Your function should handle such a case. If the user needs to know how your function works and might need to edit your function, then it isn't working well.
Such limitations should be mentioned in the documentation of your function (which it currently lacks).
If you want to overwrite a variable with the lowest possible value, you should replace it with -inf.
%the number you were looking for is this:
-realmax
ans = -1.7977e+308
function [summa, index] = max_sum(v,n)
a=length(v);
sumvar=zeros(1,a-(n-1)); %preallocating a vector (you can skip this for now_go ahead and read the rest of the code)
%for invalid input
if n>a
summa=0;
index=-1;
return;
end
%assume a matrix on your own and try running i and j using the formula below, you'll get it
for i=1:(a-(n-1))
sumtemp=0;
for j=i:(n+i-1)
sumtemp=sumtemp+v(j);
end
sumvar(i)=sumtemp;%takes the sum and catenates into a vector sumvar _ that was preallocated to save some computational time
end
[summa,index_temp]=max(sumvar(:)); % if you give two output arguments to a max function, the second argument returns index of that element
index=index_temp; % the index of the maximum number in the vector sumvar happens to be also the index of our first number in the sequence
end
function [summa,index] = max_sum(v,n)
if n > length(v)
summa = 0;
index = -1;
end
if n <= length(v)
summa = sum(v(1:n));
index = 1;
for i = 1:length(v)-n
if sum(v(i+1:i+n)) > summa
summa = sum(v(i+1:i+n));
index = i+1;
else
continue;
end
end
end
function [summa,index]=max_sum(v,n)
Z=length(v);
summ=(1:Z-n+1);
if n>Z
summa=0;
index=-1;
return;
else
for i=1:(Z-n+1)
summ(i)=sum(v(i:(i+n-1)));
end
end
[summa,index]=max(summ);
function [summa, index] = max_sum (v, n)
if n < 0 || n ~= fix(n) || ~isrow(v)
error('Input must be an integer');
elseif n > length(v)
summa = 0;
index = -1;
end
total = 0;
l = length(v);
for i = 1:l-(n-1)
total(i) = sum(v(i:i+(n-1)));
summa = max(total);
index_1 = find(total == summa);
index = min(index_1);
end
function [summa,index] = max_sum(v, n)
b = zeros(1,n);
a = find(v == max(v));
for ii = 1:n
b(ii) = max(max(v));
if find(v==b(ii),1) < a
a = find(v==b(ii),1);
end
v(find(v==max(v),1)) = 0;
end
if n > length(v)
summa = 0;
index = -1;
else
summa = sum(b);
index = a;
end

1 Comment

i tested it it with variety of inputs and it works but still i get this error;
Assessment result: incorrectrandom vectors
Variable summa has an incorrect value. max_sum([ 53 -40 60 -76 -18 31 -61 67 60 75 -60 -2 60 51 -54 -10 -4 -48 -39 80 90 96 53 88 ], 5) returned sum = 429 and index = 10 which is incorrect...
function [summa,index]=max_sum(v,n)
len=length(v); %v的長度
if(n>length(v)) %n大於v的長度
summa=0;
index=-1;
return;
else
temp_sum=zeros(1,len-n+1);
for x=1:len-n+1
temp_sum(x)=sum(v(x:x+n-1));
end
[summa,index]=max(temp_sum);
end
end % end of function

1 Comment

Still very samey ...
But I'll grant you that you've made some minor improvements, including the addition of a few comments. Next try adding formatting.
If you want to post answers, it's probably best to start with a thread that still has room for unique answers.
function [sumnma,index]=max_sum (v,n)
L = length(v);
summa = zeros(1,L-n+1);%pre-allocation
if n>L
summa = 0;
index = -1;
return
else
for i = 1:(L-n+1) %L-n+1 is the last 'first' element to be considered
summa(i)=sum(v(i:(i+n-1))); %all possible sums
end
[summa,index]=max(summa) %return the max sum and the index
end

This question is locked.

Categories

Asked:

on 19 May 2020

Locked:

on 3 Jul 2024

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!