Greedy - Post, Code and Quiet Time.

Post, Code and Quiet Time.

Sign in Subscribe

Greedy

A collection of 5 posts

Forward-Backward Traversal,

Maximum Subarray II

Question: Given an array of integers, find two non-overlapping subarrays which have the largest sum. The number in each subarray should be contiguous. Return the largest sum. Notice The subarray should contain at least one number Answer: class Solution { public: /* * @param nums: A list of integers * @return: An integer denotes

Candy

Question: http://www.lintcode.com/en/problem/candy/ There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a higher rating get more

Course Schedule III

Question: http://www.lintcode.com/en/problem/course-schedule-iii/ There are ·n· different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dth day. A course should be taken continuously for t days and must be finished before or on the dth

dynamic programming

Wildcard Matching

Question: http://www.lintcode.com/en/problem/wildcard-matching/ Implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). Answer: class Solution

Maximum Subarray

Question: http://www.lintcode.com/en/problem/maximum-subarray/ Given an array of integers, find a contiguous subarray which has the largest sum. Time Complexity: O(n) Answer: void maxsumofsubarray(int* array, int len) { int curMax = 0; int mi = -1; int mj = -1; int max; bool max_init = false; for (int