动态规划-最大子数组

时间:2022-11-29 16:55:17

1.分而治之

动态规划-最大子数组

1.分开

2.求合并的值

4.比较左右的与合并,返回最大值


2.动态规划

动态规划-最大子数组


1.求出以每个元素开头的最大数组。

d[i]:以arr[i]开头的最大数组

子问题:d[i+1]=d[i]+arr[i]

若后面规模更小的d[i]是大于0,那么d[i+1]就是自己开头的元素加上d[i]

方向:从后往前,

2.比较每个子数组,比出最大的子数组。