NoRepeat.cs

NoRepeatArr.cs

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