public int MaxEnvelopes(int[,] envelopes) { if(envelopes == null || envelopes.Length == 0){ return 0; } // 0. model the PRoblem var arr = new List<Doll>(); var rowCount = envelopes.Length / 2; for (var i = 0;i < rowCount; i++){ arr.Add(new Doll(envelopes[i,0], envelopes[i,1])); } // 1. sort the arrays arr = arr.OrderBy(x=>x).ToList(); var result = new int[rowCount]; for (var i = 0;i < rowCount; i++){ // fetch the item from first to last result[i] = 1; for (var j = i-1;j >=0 ; j--){ if(arr[i].Width > arr[j].Width && arr[i].Height > arr[j].Height){ result[i] = Math.Max(result[i], result[j]+1); } } } //Console.WriteLine(result); var max = result.Max(); return max; } public class Doll : IComparable { public int Width; public int Height; public Doll(int width, int height){ this.Width = width; this.Height = height; } public int CompareTo(object obj){ var to = (Doll)obj; if(Width!=to.Width){ return Width - to.Width; }else{ return Height - to.Height; } } }
新闻热点
疑难解答