动态规划求集合的第二大值 java 实现

MaxValueVO.java：

import lombok.Getter;
import lombok.Setter;

import java.io.Serializable;


@Getter
@Setter
public class MaxValueVO implements Serializable {

    private Integer max;
    private Integer secondMax;

}

Test.java：

import com.alibaba.fastjson.JSONObject;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.UUID;


public class Test {


    public static void main(String[] args) {
        Random random = new Random();
        List<Integer> nums = new ArrayList<>();
        for (int i = 0; i < 20; i++) {
            nums.add( random.nextInt( 100 ) );
        }
        querySecondMax( nums );
    }

    private static void querySecondMax(List<Integer> nums) {
        MaxValueVO[] dp = new MaxValueVO[ nums.size() ];
        int size = nums.size();
        // dp[i][0] 存储的是最大的
        // dp[i][1] 存储的第二大的
        // 1 2 3

        for (int i = 0; i < size; i++) {
            int num = nums.get( i );
            MaxValueVO vo = new MaxValueVO();
            if( i==0 ){
                vo.setMax( num );
                vo.setSecondMax( num );
            }else {
                MaxValueVO vo_prev = dp[ i-1 ];
                if( num > vo_prev.getMax() ){
                    vo.setMax( num );
                    vo.setSecondMax( vo_prev.getMax() );
                }else {
                    vo.setMax( vo_prev.getMax() );
                    if( num > vo_prev.getSecondMax() ){
                        vo.setSecondMax( num );
                    }else {
                        vo.setSecondMax( vo_prev.getSecondMax() );
                    }
                }
            }
            dp[i] = vo;
        }
        System.out.println(JSONObject.toJSONString( nums ));
        MaxValueVO maxValue = dp[nums.size() - 1];
        System.out.println( "最大值：" + maxValue.getMax() );
        System.out.println( "第二大值：" + maxValue.getSecondMax() );
    }
}

输出示例：

[49,15,65,1,91,41,45,95,40,5,49,85,21,28,64,73,0,75,33,58]
最大值：95
第二大值：91