liyonghelpme · April 22, 2020 04:56 · Apr 22, 2020
diff --git a/NoRepeatArr.cs b/NoRepeatArr.cs
@@ -0,0 +1,90 @@
+
+using System;
+using System.Collections.Generic;
+using System.Text.Json;
+
+
+using VT = System.ValueTuple<int, int>;
+class NoRepeatArr{
+	Dictionary<VT, int> cache = new Dictionary<VT, int>();
+	Dictionary<VT, VT> nextState = new Dictionary<VT, VT>();
+	Dictionary<VT, int> choosePos = new Dictionary<VT, int>();
+	int MaxS(int startPos, int leftK){
+		//无法选择了
+		if(startPos > (Ar.Length-Len)) return 0;
+		//没有了
+		if(leftK == 0) return 0;
+		var totalLen = leftK*Len;
+
+		var key = (startPos, leftK);
+		//必须选择了
+		if(startPos == (Ar.Length- totalLen) ){
+			var tv = 0;
+			if(startPos > 0){
+				tv = sumArr[startPos+totalLen-1]-sumArr[startPos-1];
+			}else {
+				tv = sumArr[startPos+totalLen-1];
+			}
+			choosePos.Add(key, startPos);
+			return tv;
+		}
+		if(cache.ContainsKey(key)) return cache[key];
+
+		//使用当前元素
+		var sv = 0;
+		if(startPos > 0){
+			sv = sumArr[startPos+Len-1] - sumArr[startPos-1];
+		}else {
+			sv = sumArr[startPos+Len-1];
+		}
+		var mv1 = sv + MaxS(startPos+Len, leftK-1);
+		var mv2 = MaxS(startPos+1, leftK);
+		if(mv1 >= mv2){
+			nextState.Add(key, (startPos+Len, leftK-1));
+			choosePos.Add(key, startPos);
+		}else {
+			nextState.Add(key, (startPos+1, leftK));
+		}
+		var maxV = Math.Max(mv1, mv2);
+		cache.Add(key, maxV);
+		return maxV;
+	}
+	int[] Ar;
+	int Len;
+	List<int> sumArr = new List<int>();
+	public int[] MaxSum(int[] arr, int k){
+		Ar = arr;
+		var sum = 0;
+		for(var i = 0; i < arr.Length; i++){
+			sum += arr[i];
+			sumArr.Add(sum);
+		}
+		Len = k;
+		var mv = MaxS(0, 3);
+		// Console.WriteLine(mv);
+		var lstSel = new List<int>();
+		var startState = (0, 3);
+		if(choosePos.ContainsKey(startState)){
+			lstSel.Add(choosePos[startState]);
+		}
+		while(nextState.ContainsKey(startState)){
+			var next = nextState[startState];
+			if(choosePos.ContainsKey(next)){
+				lstSel.Add(choosePos[next]);
+			}
+			startState = next;
+		}
+		// Console.WriteLine(JsonSerializer.Serialize(lstSel));
+		while(lstSel.Count  < 3){
+			var last = lstSel[lstSel.Count-1];
+			lstSel.Add(last+Len);
+		}
+		return lstSel.ToArray();
+	}
+	//  static void Main(string[] args)
+	//  {
+	// 	 var ms = new NoRepeatArr();
+	// 	 var r = ms.MaxSum(new int[]{1,2,1,2,6,7,5,1}, 2);
+	// 	Console.WriteLine(JsonSerializer.Serialize(r));
+	//  }
+}