算法【最大子序列问题】

　　　　　问题描述：

　　　　　　　　（这个问题描述可能不太准确 是根据我个人的理解写出来的）

　　　　　　　　 输入一个序列的数字 求他的最大子序列 包括空集合

　　　　　　　　例如说 1 , 2 ，3

　　　　　　　　 那么他的子序列就是 【 [1,2,3] [1,2] [1,3] [2,3] [ 1 ] [2 ] [3] [] 】

　　　　　　　　我的解决思路是通过递归调用

　　　　　　　　1. 每个元素有两种状态，一种状态是取当前元素，一种状态是不取当前元素 所以需要 一个单独的辅助数组 用来记录当前元素是否取

　　　　　　　　　　　取完所有取当前元素的子情况，就获取所有不取当前元素的子情况

　　　　　　　　2. 需要一个索引记录 当前循环到的层数，如果获取完所有元素就添加到List中

　　　　　代码：

代码语言：javascript复制

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public static boolean v[] = new boolean[100];
    public static List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public void robot(int idx, int[] nums) {
        if (idx >= nums.length) {
            List<Integer> r = new ArrayList<Integer>();
            for (int i = 0; i < nums.length;i  ) {
                if (v[i]) {
                    r.add(nums[i]);
                }
            }
            ans.add(r);
            return;
        }
        
        //这个是取当前元素的所有结果
        v[idx] = true;
        robot(idx 1,nums);
        //这个是不取当前元素的所有结果
        v[idx] = false;
        robot(idx 1,nums);
    }
    
    
    public List<List<Integer>> subsets(int [] nums)
    {
        ans.clear();
        robot(0, nums);
        return ans;
    }
    
    public static void main(String[] args) {
        for (int i = 0; i < v.length; i  ) {
            v[i] = false;
        }
        int [] nums = new int [3];
        nums[0] = 1;
        nums[1] = 2;
        nums[2] = 3;
    
        Solution solution = new Solution();
        List<List<Integer>> list = solution.subsets(nums);
        System.out.println(list);
        
    }
    
}

list 递归 数组 索引

0 人点赞