最大子序列和

本是古典何须时尚 2022-06-03 02:00 216阅读 0赞

> 给定一个整数序列，a0, a1, a2,…, an（序列项可以为负数），求其中最大的子序列和，如果所有整数都是负数，那么最大子序列和为0；

*  首先定义两个变量：**max\_so\_far**和**max\_ending\_here**
 *  然后从左到右开始遍历输入序列，其中：**max\_ending\_here**用以表示序列中截止到当前位置的最大子序列和，**max\_so\_far**则是通过冒泡排序的方式获取**max\_ending\_here**的最大值
 *  如何判断当前值是否位置最大子序列中，判断条件如下：**max\_ending\_here + list\[i\] >= 0**
 *  如果当前位置值被加入到了最大子序列中，则将当前位置索引记录，并赋予pos，记住pos即是最大子序列的开始索引

## 算法如下，具体逻辑参见注释 ##

def find_mss(list):
        # 最大子序列和开始位置
        start_pos = -1
        # 最大子序列和结束位置
        end_pos = -1
        pos = -1
        # 最大子序列和
        max_so_far = 0
        # 截止到当前位置的最大子序列和
        max_ending_here = 0
    
        for i in range(0, len(list)):
            # 判断当前值是否可以添加到最大和子序列中
            if max_ending_here + list[i] < 0:
                max_ending_here = 0
                pos = -1
            else:
                max_ending_here = max_ending_here + list[i]
                # 只有pos等于-1时，才做赋值处理，即：第一次将当前位置的值添加到最大子序列中时的索引
                if pos == -1:
                    pos = i
    
            # 冒泡比较，max_so_far确保始终是最大的
            if max_so_far < max_ending_here:
                max_so_far = max_ending_here
                start_pos = pos
                end_pos = i
    
        print("Maximum sum subsequence : "),
        for i in range(start_pos, end_pos + 1):
            print(list[i]),
    
        print("\nSum : %s" % max_so_far)
    
    
    if __name__ == "__main__":
        lst = [int(x) for x in input().split()]
        find_mss(lst)

[http://www.edufyme.com/code/?id=072b030ba126b2f4b2374f342be9ed44][http_www.edufyme.com_code_id_072b030ba126b2f4b2374f342be9ed44]

[http_www.edufyme.com_code_id_072b030ba126b2f4b2374f342be9ed44]: http://www.edufyme.com/code/?id=072b030ba126b2f4b2374f342be9ed44