算法【最大子序列问题】

梅花

发布于 2020-09-28 10:26:18

5520

发布于 2020-09-28 10:26:18

文章被收录于专栏：梅花的学习记录

　　　　　问题描述：

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

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

　　　　　　　　例如说 1 , 2 ，3

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

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

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

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

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

　　　　　代码：

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);
        
    }
    
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-11-17 ，如有侵权请联系 cloudcommunity@tencent.com 删除

list