you don't need to have arrays to store everything. A more memory efficient
way is to store 2 values at each iteration whether to take this number or
not. Below is a python code doing just that.
def main():
numbers = map(int, raw_input().split())
maxTakingThis = 0
maxNotTakingThis = 0
for number in numbers:
maxTakingPrevious = maxTakingThis
maxNotTakingPrevious = maxNotTakingThis
maxTakingThis = number +
max(maxTakingPrevious,maxNotTakingPrevious)
maxNotTakingThis = maxTakingPrevious
print max(maxTakingThis,maxNotTakingThis)
return 0
if(__name__=="__main__"):
main()
On Tue, Jan 12, 2016 at 9:51 PM, yomama <[email protected]> wrote:
>
> Here's a solution in javascript
> var data = [10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3];
> function max(array) {
> var i = array[0];
> array.forEach(function(val) {
> if(val > i)
> i = val;
> });
> return i;
> }
> function maxSum(i, data, canSkip) {
> var len = data.length - i;
> if( len === 1) {
> if(canSkip && data[i] < 0) {
> return 0;
> } else {
> return data[i];
> }
> } else if(len <1) {
> return 0;
> }
> var skippedI = maxSum(i + 1, data, false);
> var notSkippedISkippedJ = maxSum(i + 1, data, true) + data[i];
> var notSkippedINotSkippedJ = maxSum(i + 2, data, true) + data[i] +
(data[i+1] || 0);
> if(canSkip) {
> return max([skippedI, notSkippedISkippedJ,
notSkippedINotSkippedJ]);
> } else {
> return max([notSkippedISkippedJ, notSkippedINotSkippedJ]);
> }
> }
>
> console.log(maxSum(0, data, true));
>
> On Tuesday, March 24, 2015 at 6:47:46 AM UTC-7, atul007 wrote:
>>
>> Given a array with +ve and -ve integer , find the maximum sum such that
you are not allowed to skip 2 contiguous elements ( i.e you have to select
atleast one of them to move forward).
>>
>> eg :-
>>
>> 10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3
>>
>> Output : 10+20+30-10+40-1 = 89
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
email to [email protected].
--
- Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
