Given a list of integers, find the largest sum of a contiguous subsequence

up vote
1
down vote

favorite

Given a list of integers, find the largest sum of a contiguous sub-sequence.

1, 2, 3, 4, 5, -1, 7, -4, -2
(* 21 *)

And print the sub-array which is 1,2,3,4,5,-1,7.

I am getting 15.

LargestContiguousSum[numbers_List] := 
 Module[maxcurrent = numbers[[1]], maximumglobal = numbers[[1]], i,
 For[i = 2, i < Length[numbers], i++, 
 maxcurrent = Max[numbers[[i]], maxcurrent + numbers[[i]]];
 If[maxcurrent > maximumglobal, maximumglobal = maxcurrent]];
 maximumglobal];
LargestContiguousSum[1, 2, 3, 4, 5, -1, 7]

edited 1 hour ago

m0nhawk

2,49811531

asked 1 hour ago

Bignya ranjan Pathi

445

add a commentÂ |Â

up vote
1
down vote

favorite

Given a list of integers, find the largest sum of a contiguous sub-sequence.

1, 2, 3, 4, 5, -1, 7, -4, -2
(* 21 *)

And print the sub-array which is 1,2,3,4,5,-1,7.

I am getting 15.

LargestContiguousSum[numbers_List] := 
 Module[maxcurrent = numbers[[1]], maximumglobal = numbers[[1]], i,
 For[i = 2, i < Length[numbers], i++, 
 maxcurrent = Max[numbers[[i]], maxcurrent + numbers[[i]]];
 If[maxcurrent > maximumglobal, maximumglobal = maxcurrent]];
 maximumglobal];
LargestContiguousSum[1, 2, 3, 4, 5, -1, 7]

edited 1 hour ago

m0nhawk

2,49811531

asked 1 hour ago

Bignya ranjan Pathi

445

add a commentÂ |Â

up vote
1
down vote

favorite

Given a list of integers, find the largest sum of a contiguous sub-sequence.

1, 2, 3, 4, 5, -1, 7, -4, -2
(* 21 *)

And print the sub-array which is 1,2,3,4,5,-1,7.

I am getting 15.

LargestContiguousSum[numbers_List] := 
 Module[maxcurrent = numbers[[1]], maximumglobal = numbers[[1]], i,
 For[i = 2, i < Length[numbers], i++, 
 maxcurrent = Max[numbers[[i]], maxcurrent + numbers[[i]]];
 If[maxcurrent > maximumglobal, maximumglobal = maxcurrent]];
 maximumglobal];
LargestContiguousSum[1, 2, 3, 4, 5, -1, 7]

edited 1 hour ago

m0nhawk

2,49811531

asked 1 hour ago

Bignya ranjan Pathi

445

Given a list of integers, find the largest sum of a contiguous sub-sequence.

1, 2, 3, 4, 5, -1, 7, -4, -2
(* 21 *)

And print the sub-array which is 1,2,3,4,5,-1,7.

I am getting 15.

LargestContiguousSum[numbers_List] := 
 Module[maxcurrent = numbers[[1]], maximumglobal = numbers[[1]], i,
 For[i = 2, i < Length[numbers], i++, 
 maxcurrent = Max[numbers[[i]], maxcurrent + numbers[[i]]];
 If[maxcurrent > maximumglobal, maximumglobal = maxcurrent]];
 maximumglobal];
LargestContiguousSum[1, 2, 3, 4, 5, -1, 7]

list-manipulation array

edited 1 hour ago

m0nhawk

2,49811531

asked 1 hour ago

Bignya ranjan Pathi

445

edited 1 hour ago

m0nhawk

2,49811531

asked 1 hour ago

Bignya ranjan Pathi

445

edited 1 hour ago

m0nhawk

2,49811531

edited 1 hour ago

m0nhawk

2,49811531

edited 1 hour ago

m0nhawk

2,49811531

asked 1 hour ago

Bignya ranjan Pathi

445

asked 1 hour ago

Bignya ranjan Pathi

445

asked 1 hour ago

Bignya ranjan Pathi

445

add a commentÂ |Â

2 Answers
2

active

oldest

votes

up vote
2
down vote

accepted

f = a [Function] 
 With[A = UpperTriangularize[Outer[Plus, Join[0, -Most[#]], #, 1] &[Accumulate[a]]],
 MaximalBy[
 Flatten[MapIndexed[x, i [Function] x, i, A, 2], 1], 
 First
 ][[1]]
 ];

sum, pos = f[1, 2, 3, 4, 5, -1, 7, -4, -2]

21, 1, 7

edited 1 hour ago

answered 1 hour ago

Henrik Schumacher

40.1k255120

add a commentÂ |Â

up vote
1
down vote

Here is a brute force approach modeled after your initial approach but with Do rather than For:

LargestContiguousSum[numbers_List] := Module[n, mSum, index, sum, y, accumulate,
 n = Length[numbers];
 accumulate = Accumulate[numbers];
 mSum = Max[accumulate];
 index = 1;
 Do[sum = Max[accumulate[[i ;; n]]] - accumulate[[i - 1]];
 If[sum > mSum, mSum = sum; index = i], i, 2, n];
 y = accumulate[[index ;; n]] - If[index == 1, 0, accumulate[[index - 1]]];
 Max[y], numbers[[index ;; index + Position[y, Max[y]][[1, 1]] - 1]]]

maxSum[1, 2, 3, 4, 5, -1, 7, -4, -2]
(* 21,1,2,3,4,5,-1,7 *)

answered 30 mins ago

JimB

15.3k12657

add a commentÂ |Â

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\$","\$"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "387"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f182882%2fgiven-a-list-of-integers-find-the-largest-sum-of-a-contiguous-subsequence%23new-answer', 'question_page');

);

Post as a guest

Name

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

up vote
2
down vote

accepted

f = a [Function] 
 With[A = UpperTriangularize[Outer[Plus, Join[0, -Most[#]], #, 1] &[Accumulate[a]]],
 MaximalBy[
 Flatten[MapIndexed[x, i [Function] x, i, A, 2], 1], 
 First
 ][[1]]
 ];

sum, pos = f[1, 2, 3, 4, 5, -1, 7, -4, -2]

21, 1, 7

edited 1 hour ago

answered 1 hour ago

Henrik Schumacher

40.1k255120

add a commentÂ |Â

up vote
2
down vote

accepted

f = a [Function] 
 With[A = UpperTriangularize[Outer[Plus, Join[0, -Most[#]], #, 1] &[Accumulate[a]]],
 MaximalBy[
 Flatten[MapIndexed[x, i [Function] x, i, A, 2], 1], 
 First
 ][[1]]
 ];

sum, pos = f[1, 2, 3, 4, 5, -1, 7, -4, -2]

21, 1, 7

edited 1 hour ago

answered 1 hour ago

Henrik Schumacher

40.1k255120

add a commentÂ |Â

up vote
2
down vote

accepted

f = a [Function] 
 With[A = UpperTriangularize[Outer[Plus, Join[0, -Most[#]], #, 1] &[Accumulate[a]]],
 MaximalBy[
 Flatten[MapIndexed[x, i [Function] x, i, A, 2], 1], 
 First
 ][[1]]
 ];

sum, pos = f[1, 2, 3, 4, 5, -1, 7, -4, -2]

21, 1, 7

edited 1 hour ago

answered 1 hour ago

Henrik Schumacher

40.1k255120

f = a [Function] 
 With[A = UpperTriangularize[Outer[Plus, Join[0, -Most[#]], #, 1] &[Accumulate[a]]],
 MaximalBy[
 Flatten[MapIndexed[x, i [Function] x, i, A, 2], 1], 
 First
 ][[1]]
 ];

sum, pos = f[1, 2, 3, 4, 5, -1, 7, -4, -2]

21, 1, 7

edited 1 hour ago

answered 1 hour ago

Henrik Schumacher

40.1k255120

edited 1 hour ago

answered 1 hour ago

Henrik Schumacher

40.1k255120

answered 1 hour ago

Henrik Schumacher

40.1k255120

answered 1 hour ago

Henrik Schumacher

40.1k255120

add a commentÂ |Â

up vote
1
down vote

Here is a brute force approach modeled after your initial approach but with Do rather than For:

LargestContiguousSum[numbers_List] := Module[n, mSum, index, sum, y, accumulate,
 n = Length[numbers];
 accumulate = Accumulate[numbers];
 mSum = Max[accumulate];
 index = 1;
 Do[sum = Max[accumulate[[i ;; n]]] - accumulate[[i - 1]];
 If[sum > mSum, mSum = sum; index = i], i, 2, n];
 y = accumulate[[index ;; n]] - If[index == 1, 0, accumulate[[index - 1]]];
 Max[y], numbers[[index ;; index + Position[y, Max[y]][[1, 1]] - 1]]]

maxSum[1, 2, 3, 4, 5, -1, 7, -4, -2]
(* 21,1,2,3,4,5,-1,7 *)

answered 30 mins ago

JimB

15.3k12657

add a commentÂ |Â

up vote
1
down vote

Here is a brute force approach modeled after your initial approach but with Do rather than For:

LargestContiguousSum[numbers_List] := Module[n, mSum, index, sum, y, accumulate,
 n = Length[numbers];
 accumulate = Accumulate[numbers];
 mSum = Max[accumulate];
 index = 1;
 Do[sum = Max[accumulate[[i ;; n]]] - accumulate[[i - 1]];
 If[sum > mSum, mSum = sum; index = i], i, 2, n];
 y = accumulate[[index ;; n]] - If[index == 1, 0, accumulate[[index - 1]]];
 Max[y], numbers[[index ;; index + Position[y, Max[y]][[1, 1]] - 1]]]

maxSum[1, 2, 3, 4, 5, -1, 7, -4, -2]
(* 21,1,2,3,4,5,-1,7 *)

answered 30 mins ago

JimB

15.3k12657

add a commentÂ |Â

up vote
1
down vote

Here is a brute force approach modeled after your initial approach but with Do rather than For:

LargestContiguousSum[numbers_List] := Module[n, mSum, index, sum, y, accumulate,
 n = Length[numbers];
 accumulate = Accumulate[numbers];
 mSum = Max[accumulate];
 index = 1;
 Do[sum = Max[accumulate[[i ;; n]]] - accumulate[[i - 1]];
 If[sum > mSum, mSum = sum; index = i], i, 2, n];
 y = accumulate[[index ;; n]] - If[index == 1, 0, accumulate[[index - 1]]];
 Max[y], numbers[[index ;; index + Position[y, Max[y]][[1, 1]] - 1]]]

maxSum[1, 2, 3, 4, 5, -1, 7, -4, -2]
(* 21,1,2,3,4,5,-1,7 *)

answered 30 mins ago

JimB

15.3k12657

Here is a brute force approach modeled after your initial approach but with Do rather than For:

LargestContiguousSum[numbers_List] := Module[n, mSum, index, sum, y, accumulate,
 n = Length[numbers];
 accumulate = Accumulate[numbers];
 mSum = Max[accumulate];
 index = 1;
 Do[sum = Max[accumulate[[i ;; n]]] - accumulate[[i - 1]];
 If[sum > mSum, mSum = sum; index = i], i, 2, n];
 y = accumulate[[index ;; n]] - If[index == 1, 0, accumulate[[index - 1]]];
 Max[y], numbers[[index ;; index + Position[y, Max[y]][[1, 1]] - 1]]]

maxSum[1, 2, 3, 4, 5, -1, 7, -4, -2]
(* 21,1,2,3,4,5,-1,7 *)

answered 30 mins ago

JimB

15.3k12657

answered 30 mins ago

JimB

15.3k12657

answered 30 mins ago

JimB

15.3k12657

answered 30 mins ago

JimB

15.3k12657

add a commentÂ |Â

draft saved

draft discarded

draft saved

draft discarded

Post as a guest

Name

Search This Blog

Iyfjky