Greatest subsequence product

Use the following python code to get a generator for the subsequences of a sequence:

def subsequences(li):
    for length in xrange(1, len(li) + 1):
        for start in xrange(0, len(li) - length + 1):
            yield li[start : start + length]

Then, use this python code to find the maximum product of a subsequence, by first extracting the data into a list of ints, then iterating over every subsequence and replacing the "ans" variable with the product if the product is greater than it.

import urllib2
ans = 0
data = map(int, urllib2.urlopen('https://gist.githubusercontent.com/brilliant-problems/9359971f37e7460dd30b/raw/3793fb282b24dab4d6718540e7521f909d37711e/cs_greatestproduct').read().split())
for i in subsequences(data):
    product = reduce(lambda a, b: a * b, i)
    if product > ans:
        ans = product
print ans

Another problem that can be done using a rolling window.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

from operator import mul

allNumbers=[0, 3, -5, 2, 1, 2, 1, -3, 4, -1, -2, -2, -1, 5, 4, -2, 1, 4, 5, 4, -1, -1, 0, 2, 1, -4, 0, 1, 0, -5, 4, -1, -1, -3, 0, -5, -2, 2, -2, 2, 3, -4, 1, 5, 1, 2, 0, -5, -3, 5, 0, 2, 5, 1, -5, 2, 3, 0, 4, -4, 4, 3, 1, 3, 5, -2, -1, 5, 3, -3, 5, 3, -3, 5, -5, 5, -1, -5, 0, -4, 5, 5, 0, -3, -1, 2, 5, 5, -1, -4, -4, 5, -4, -2, 5, -4, -1, 0, 4, 4]

def rollingWindow(seq, window_size):
    it = iter(seq)
    win = [it.next() for cnt in xrange(window_size)] 
    yield win
    for e in it: 
        win[:-1] = win[1:]
        win[-1] = e
        yield win

P=0
for size in range(1, 1+len(allNumbers)):
    for rw in rollingWindow(allNumbers, size):
        P=max(P,reduce(mul,rw,1))
print P

Use 0 to separate the list into sub sequences. If a sub sequence has even number of negatives in it, then its max value is the product of all numbers in it. If a sub sequence has odd number of negatives in it, we use each negative number as a divider and has the list divided into the left and right side. We find max value of the sequence by compare all left sides and right sides. Note that this method is based on a condition: every number in the list has the absolute value equal or greater than 1.

This is the code (written in Boo):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

def max3(a, b, c):
    r=a;

    if r<b:
        r=b;

    if r<c:
        r=c;

    return r;

def mul(list, left, right):
    value as double=1;

    for i in range(left, right):
        value*=list[i];

    return value;

def gsp(list):
    zeropos=[];
    for i in range(0, len(list)):
        if list[i]==0:
            zeropos.Add(i);

    max as double=0;
    negativepos=[];

    for i in range(0, len(zeropos)-1):
        l=zeropos[i]+1;
        r=zeropos[i+1];

        if r<=l:
            continue;

        negativepos.Clear();

        for j in range(l, r):
            if list[j]<0:
                negativepos.Add(j);

        if len(negativepos)%2==0:
            v=mul(list, l, r);
            if v>max:
                max=v;
        else:           
            for k in negativepos:
                lv=mul(list, l, k);
                rv=mul(list, k+1, r);
                max=max3(max, lv, rv);  
    return max;

list=[0,3,-5,2,1,2,1,-3,4,-1,-2,-2,-1,5,4,-2,1,4,5,4,-1,-1,0,2,1,-4,0,1,0,-5,4,-1,-1,-3,0,-5,-2,2,-2,2,3,-4,1,5,1,2,0,-5,-3,5,0,2,5,1,-5,2,3,0,4,-4,4,3,1,3,5,-2,-1,5,3,-3,5,3,-3,5,-5,5,-1,-5,0,-4,5,5,0,-3,-1,2,5,5,-1,-4,-4,5,-4,-2,5,-4,-1,0,4,4]
print gsp(list);

My solution is separate the sequence into sub-sequences with 0 as the separator, then evaluate each all possible sub-sub-sequence. First three digits from ans is the answer.

l = [0, 3, -5, .... 4, 4]
z = []
for i in range(len(l) - 1):
    if l[i] is 0:
        z.append(i)
z.append(len(z)-1)

ans = 0;
for i in range(0, len(z) - 2):
    p = (z[i + 1] - z[i]);
    for j in range(2,  p):
        for k in range(z[i] + 1, z[i] + p - j + 1):
            prod = 1;
            for m in range(k, k + j):
                prod = prod * l[m]
            if prod > ans:
                ans = prod

4 -4 4 3 1 3 5 -2 -1 5 3 -3 5 3 -3 5 -5 5 -1 -5 find this sequence and multiply............so simple.

In AutoHotkey

global file := A_Desktop "\nlist.txt"   ; THE FILE WITH THE LIST

pro := 1 , x := 1 , o := {}
loop, read, % file 
    o.Insert(A_LoopReadLine)
l := o.maxIndex()

loop % l {
    z := A_Index
    loop % l-z+1
    {
        x *= o[z-1+A_index]
        if (x>pro)
            pro := x
    }
    x := 1
}

msgbox % pro