Codewars Java练习:Maximum subarray sum

题目

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:

Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

题解

哇,终于做到动态规划了耶,将数组A本身转化为前缀和数组B,那么本题就是要求在前缀和数组B上找一前一后两个数,使得他们的差尽量大。

当然,这样的做法较为繁琐,可以一个for语句解决的事情就不要用多个,下面是我的代码——

其中,sum储存的是在某个位置结束的数组A的子序列最大字段和,为什么有这样的更新方法读者自己试一组样例就知道了。

原创文章地址:【Codewars Java练习:Maximum subarray sum】,转载时请注明出处mhy12345.xyz

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据