Lists in the python

Question

1. We have to accept a list and find the subsequent from the list such that number in subsequence are in increasing order.
2. Find sum of each subsequence
3. return maximum sum

For example

Input=[1, 4,2]

Possible subsequence will be [1][4][2][1,4][1,2]
Here [4,2] will not come as 4 is greater. And order should not change. Means first position elements if it comes in sublist it should be first

Sum of each subsequence will be 1,4,2,5,3 Output will be 5.

What will be your logic to solve it?

Answer 1

You can use itertools.combinations and itertools.chain to do this easily

>>> from itertools import combinations, chain
>>> Input=[1, 4,2]
>>> max(map(sum, (filter(lambda x: sorted(x) == list(x), chain(*[combinations(Input, i) for i in range(1, len(Input)+1)])))))
5

Explanation

>>> possibilities = chain(*[combinations(Input, i) for i in range(1, len(Input)+1)])
>>> filtered_possibilities = filter(lambda x: sorted(x) == list(x), possibilities)
>>> sum_of_each_possibility = map(sum, filtered_possibilities)
>>> max_sum = max(sum_of_each_possibility)
>>> print (max_sum)
5

Answer 2

You can break down the question into three steps:

1) Find the power_set(all sub lists) of list.

2) Filter out unwanted list (list with decreasing order).

3) Find the max sum.

Step1:

def powerset(s):
    x = len(s)
    res=[]
    for i in range(1 << x):
        res.append([s[j] for j in range(x) if (i & (1 << j))])
    return res

lst=[1,4,2]
res=powerset(lst)

Step 2&3:

def max_sub(lsts):
    max_out=0
    def helper(lsts): #Step2: to filter out decreasing lists.
        if lsts==[]:
            return False
        else:
            for i in range(len(lsts)-1):
                if lsts[i]>lsts[i+1]:
                    return False
        return True
    filtered_lst=list(filter(lambda x:helper(x),lsts))
    for lst in filtered_lst:
        max_out=max(max_out,sum(lst))    #step3: Find out the max sub list sum.
    return max_out
print(max_sub(res))

Result:

5

Answer 3

Drako already mentioned, that this is not free coding service. Show some effort yourself and tell us, what you already tried and how it didn't work. also provide output to help us analyze the problem. I'll help anyway; also welcome to StackOverflow.

What you are looking for is a "power set". An exhaustive set M of sets s, where each s is a subset of M and there is in fact no subset of M which is not already contained in a s. As sets are unordered by definition, you don't have to care about duplicates because of different ordering. Looking at this question

There is a nice answer to get the power set of a given set. Assuming your input list/set/iterable is i, you can use the following code to get the power set list.

from itertools import chain, combinations

def get_power_set(i):
    i.sort()    # Sorted input --> sorted output
    ps_iterable = chain.from_iterable(combinations(i, r) for r in range(len(i)+1))
    return list(ps_iterable)

def get_highest_sum(input_list):
    maximum = 0
    for s in input_list:
        sum_of_set = sum(s)
        if sum_of_set > maximum:
            maximum = sum_of_set
    return maximum

i = [1,2,3]     # Assign your input list here

power_set = get_power_set(i)
highest_sum = get_highest_sum(power_set)

print(power_set)
# >>> [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
print("Highest sum is {}".format(highest_sum))
# >>> 6