环形子数组的最大值
Kanade算法 对于普通数组求最大子数组和
int cur=nums[0];int ans=nums[0];
for(int i=1;i<n;i++){
cur=nums[i]+Math.max(0,cur);
ans=Math.max(ans,cur);
}
通过kanade算法计算单个子数组最大子数组和
通过后缀计算双子数组最大和
class Solution {
public int maxSubarraySumCircular(int[] nums) {
//通过前缀和的方式计算对应的
//对于一段子数组的最大和‘
int cur=0;int ans=0;
int n=nums.length;
for(int i=0;i<nums.length;i++){
//对于当前和元素结尾得子数组和
cur=nums[i]+Math.max(cur,0);
ans=Math.max(ans,cur);
}
//对于双端子数组
//通过数组维护后缀
int[] subfix=new int[n];
subfix[n-1]=nums[n-1];
for(int i=n-2;i>=0;i--){
subfix[i]=subfix[i+1]+nums[i];
}
//对于后缀最大值
int[] maxSubfix=new int[n];
maxSubfix[n-1]=subfix[n-1];
for(int i=n-2;i>=0;i--){
maxSubfix[i]=Math.max(maxSubfix[i+1],subfix[i]);
}
//对于双端
int leftSum=0;
for(int i=0;i+2<n;i++){
leftSum+=nums[i];
ans=Math.max(ans,leftSum+maxSubfix[i+2]);
}
return ans;
}
}
煎饼排序
class Solution {
public List<Integer> pancakeSort(int[] nums) {
List<Integer> res=new ArrayList<Integer>();
for(int n=nums.length;n>1;n--){
int index=0;
for(int i=1;i<n;i++){
if(nums[i]>=nums[index]){
index=i;
}
}
//将最大值交换
if(index==n-1){
continue;
}
reverse(nums,index);
reverse(nums,n-1);
res.add(index+1);
res.add(n);
}
return res;
}
public void reverse(int[] nums,int end){
for(int i=0,j=end;i<j;i++,j--){
int t=nums[i];
nums[i]=nums[j];
nums[j]=t;
}
}
}