1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 42 题] “连续子数组的最大和”做题记录

[剑指 Offer 第 2 版第 42 题] “连续子数组的最大和”做题记录

第 42 题:连续子数组的最大和

传送门:连续子数组的最大和牛客网 online judge 地址

输入一个 非空 整型数组,数组里的数可能为正,也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为 O(n)

样例:

输入:[1, -2, 3, 10, -4, 7, 2, -5]

输出:18

同 LeetCode 第 53 题,题解传送门:LeetCode 第 53 题:连续子数组的最大和

“大雪菜”的做法:状态:以前一个数结尾的“连续子数组的最大和”为状态。

C++ 代码:

liwei2019101117_1.png

分析:

  • 根据“最长公共子序列”问题的思路,我们在考虑数组的时候,定义以当前数组元素为结尾的连续子数组,往往会使用情况变得简单一些。
  • 设置状态:dp[i]i 结尾的子数组的最大和。
  • 考虑状态转移方程:

如果 nums[i] < 0,dp[i] = max(dp[i-1] + nums[i],nums[i]); 如果 nums[i] >= 0,dp[i] = dp[i-1] + nums[i];

综上所述,不论当前考虑的数组元素是大于等于 0 还是小于 0,只要满足 dp[i] = max(dp[i-1] + nums[i], nums[i]) 就可以了,这就是状态转移方程。

Java 代码:

  public class Solution {

        public int FindGreatestSumOfSubArray(int[] array) {
            int n = array.length;
            if (n == 0) {
                return 0;
            }
            int[] dp = new int[n];
            dp[0] = array[0];
            int res = array[0];
            for (int i = 1; i < n; i++) {
                dp[i] = Integer.max(dp[i - 1] + array[i], array[i]);
                res = Integer.max(res, dp[i]);
            }
            return res;
        }

        public static void main(String[] args) {
            int[] nums = new int[]{6, -3, -2, 7, -15, 1, 2, 2};
            Solution solution = new Solution();
            int findGreatestSumOfSubArray = solution.FindGreatestSumOfSubArray(nums);
            System.out.println(findGreatestSumOfSubArray);
        }
    }

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 42 题] “连续子数组的最大和”做题记录

链接:https://www.javajike.com/article/3289.html

« [剑指 Offer 第 2 版第 41 题] “数据流中的中位数”做题记录
[剑指 Offer 第 2 版第 44 题] “数字序列中某一位的数字”做题记录»

相关推荐

QR code