首页
登录 | 注册

[动态规划试炼]最大连续数列和

春风十里扬州路,卷上珠帘总不如。 ——杜牧《赠别》

对于一个有正有负的整数数组,请找出总和最大的连续数列。
给定一个int数组A和数组大小n,请返回最大的连续数列的和。保证n的大小小于等于3000。
测试样例:

[1,2,3,-6,1]
返回:6

解题步骤,分析四要素:

  • 状态定义:F(i):以A[i]结尾的连续最大子序列的和;
  • 递推:F(i) = max(F(i)+A[i],F(i));
  • 状态初始化: F(1) = A[0];
  • 返回结果:max(F(i));
import java.util.*;
public class MaxSum {
    public int getMaxSum(int[] A, int n) {
        //初始化,有正有负,那么最大值应该就是正值。
        //记录当前最大值
        int max = A[0];
        //总的和
        int sum = 0;
        //递推
        for(int i= 0;i < n; i ++){
            //累积最大和
            sum += A[i];
            //本次与上一次比较
            max = Math.max(sum,max);
            if(0 > sum) sum = 0 ;
        }
        //返回结果
        return max;
    }
}


2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.008 s.
京ICP备10005923号