java 剑指offer之[数据结构简单]JZ42 连续子数组的最大和题目大意一、示意图二、解题思路

151 阅读 0 评论 100 点赞

我是靠谱客的博主优雅鞋子，这篇文章主要介绍java 剑指offer之[数据结构简单]JZ42 连续子数组的最大和题目大意一、示意图二、解题思路，现在分享给大家，希望可以做个参考。

题目的链接在这里：https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484

题目大意

输入一个长度为n的整型数组a，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).

提示:
1 <= n <= 500
-100 <= a[i] <= 100

一、示意图

在这里插入图片描述

二、解题思路

复制代码

1
2
动态规划

动态规划

代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
 public int FindGreatestSumOfSubArray(int[] array) {
                //连续子数组的最大和
                //这里是以某一个为结尾的 那就必定能把所有的 都遍历一遍
                //dp[i]表示是以array[i]为结尾的 最大值 那就必须要有array[i]
                //如果array[i]是正数就加
                int dp[]=new int[array.length];
                dp[0]=array[0];
                int max=array[0];
                //然后开始判断
                for(int i=1;i<array.length;i++){
                        if(dp[i-1]>0){
                                dp[i]=dp[i-1]+array[i];
                        }
                        else{
                                //如果小于0的话 那就不进行删除吗
                                dp[i]=array[i];
                        }
                        //然后顺便更新一下最大值
                        if(dp[i]>max){
                                max=dp[i];
                        }
                }
                
                return max;
        }
}