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 <binh.p...@gmail.com> 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 algogeeks+unsubscr...@googlegroups.com.
--
- 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 algogeeks+unsubscr...@googlegroups.com.
