动态规划（Dynamic Programming，DP） 求连续子数组的最大和_求和最大的连续子数组动态规划

动态规划中的每一个状态一定是由上一个状态推导而来，这一定区别与贪心算法，贪心没有状态推导，而是局部直接选最优的

转态规划解题步骤

：
状态规划的状态转移公式是很重要的，但是动态规划不仅仅只有递推公式

将其分为以下五步曲，就可以讲动态规划掌握

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组
以上理论来源 参考公众号，代码随想录，

下面这个例子来源牛客剑指offer
题目描述
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n)
.
**

思路分析：

**

1、状态方程 ： max( dp[ i ] ) = getMax( max( dp[ i -1 ] ) + arr[ i ] ,arr[ i ] )
上面式子的意义是：我们从头开始遍历数组，遍历到数组元素 arr[ i ] 时，连续的最大的和 可能为 max( dp[ i -1 ] ) + arr[ i ] ，也可能为 arr[ i ] ，做比较即可得出哪个更大，取最大值。时间复杂度为 n
2 数组初始化以及遍历for循环从前带后就可

代码如下

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int len = array.length;
           if (len == 0){
            return 0;
           }
         //  int[] currentsum = new int[len];
      int     currentsum = array[0];
           int greatsetsum = array[0];
        
        for(int i=1;i<array.length;i++){
            //动态规划的转移方程
           /* if (currentsum[i-1]>0){
                currentsum[i]=currentsum[i-1]+array[i];
            }
            else {
                currentsum[i]=array[i];
            }
            */
            currentsum=currentsum>0?currentsum+array[i]:array[i];
            //更新最大值
            
            //if(currentsum[i]>greatsetsum){
            greatsetsum= Math.max(currentsum,greatsetsum);
                 //greatsetsum=currentsum[i];
           //}
           
        }
   return greatsetsum;
   
    }
}

//主要定义一个最大子数组和great，累加子数组和sum


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
29
30
31
32
33
34
35
36