Clean Simple Well-Structured DP Java Solution


  • 0
    M
        public int findNumberOfLIS(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            int maxLen = 1;
            int maxCnt = 1;
            int n = nums.length;
            int[] lens = new int[n];
            int[] cnts = new int[n];
            Arrays.fill(lens, 1);
            Arrays.fill(cnts, 1);
            for (int i = 1; i < n; ++i) {
                for (int j = 0; j < i; ++j) {
                    if (nums[i] > nums[j] && lens[j] + 1 >= lens[i]) {
                        if (lens[j] + 1 > lens[i]) {
                            lens[i] = lens[j] + 1;
                            cnts[i] = cnts[j];
                        } else {
                            cnts[i] += cnts[j];
                        }
                    }
                }
                if (lens[i] >= maxLen) {
                    if (lens[i] > maxLen) {
                        maxLen = lens[i];
                        maxCnt = cnts[i];
                    } else {
                        maxCnt += cnts[i];
                    }
                }
            }
            return maxCnt;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.