【每日算法】动态规划五

• 918.环形子数组的最大和
• 152.乘积最大子数组
• 1567.乘积为正数的最长子数组长度

难度[中等]

给定一个由整数数组 A 表示的环形数组 C，求 C 的非空子数组的最大可能和。

&#x5728;&#x6B64;&#x5904;&#xFF0C;&#x73AF;&#x5F62;&#x6570;&#x7EC4;&#x610F;&#x5473;&#x7740;&#x6570;&#x7EC4;&#x7684;&#x672B;&#x7AEF;&#x5C06;&#x4F1A;&#x4E0E;&#x5F00;&#x5934;&#x76F8;&#x8FDE;&#x5448;&#x73AF;&#x72B6;&#x3002;&#xFF08;&#x5F62;&#x5F0F;&#x4E0A;&#xFF0C;&#x5F53;0 <= i < a.length 时 c[i]="A[i]&#xFF0C;&#x4E14;&#x5F53;&#xA0;i">= 0&#xA0;&#x65F6;&#xA0;C[i+A.length] = C[i]&#xFF09;

&#x6B64;&#x5916;&#xFF0C;&#x5B50;&#x6570;&#x7EC4;&#x6700;&#x591A;&#x53EA;&#x80FD;&#x5305;&#x542B;&#x56FA;&#x5B9A;&#x7F13;&#x51B2;&#x533A; A&#xA0;&#x4E2D;&#x7684;&#x6BCF;&#x4E2A;&#x5143;&#x7D20;&#x4E00;&#x6B21;&#x3002;&#xFF08;&#x5F62;&#x5F0F;&#x4E0A;&#xFF0C;&#x5BF9;&#x4E8E;&#x5B50;&#x6570;&#x7EC4;&#xA0;C[i], C[i+1], ..., C[j]&#xFF0C;&#x4E0D;&#x5B58;&#x5728;&#xA0;i <= 2 3 5 k1, k2 <="j&#xA0;&#x5176;&#x4E2D;&#xA0;k1" % a.length ="k2" a.length）   示例 1： 输入：[1,-2,3,-2] 输出：3 解释：从子数组 [3] 得到最大和 2： 输入：[5,-3,5] 输出：10 [5,5] + 3： 输入：[3,-1,2,-1] 输出：4 [2,-1,3] (-1) 4： 输入：[3,-2,2,-3] 和 [3,-2,2] 都可以得到最大和 5： 输入：[-2,-3,-1] 输出：-1 [-1] -1 code></=></=>

分两种情况：

1. 无环的情况
   此时和数组最大子序列和的解法一样。
2. 有环的情况
   为了使第一个和最后一个子区间的和尽可能大，中间子区间的和应该尽可能小，然后从数组的和中减去最小序列的和，这是第一个和最后一个子区间的最大值。
   [En]

   To make the sum of the first and last subintervals as large as possible, the sum of the middle subintervals should be as small as possible, and then subtract the sum of the smallest sequence from the sum of the array, which is the maximum of the first and last subintervals.

输入验证码查看隐藏内容

扫描二维码关注本站微信公众号 Johngo学长

或者在微信里搜索 Johngo学长

回复 svip 获取验证码

Johngo学长