子序列在整型数组最大总和 [英] Subsequence with maximum sum in array of ints

问题描述

由于整数数组，你怎么能找到两个指数，i和j，使得在子数组起始元素的总和，并在指数结束最大化，线性时间？

Given an array of integers, how can you find two indices, i and j, such that the sum of the elements in the subarray starting and ending at the indices is maximized, in linear time?

推荐答案

从我的编程珍珠的：

maxsofar = 0
maxendinghere = 0
for i = [0, n)
    /* invariant: maxendinghere and maxsofar are accurate
       are accurate for x[0..i-1] */
    maxendinghere = max(maxendinghere + x[i], 0)
    maxsofar = max(maxsofar, maxendinghere)

这篇关于子序列在整型数组最大总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！