P7阿里面试题2020.07 之滑动窗算法(阿里云面试)

迈不过友情╰ 2023-02-26 08:28 5阅读 0赞

题目是有一个数据之中的数字可能为正负整数，求连续n个数之和的最大值。

其实就是双指针滑动记录循环中的最大值。

实现：

import java.math.BigDecimal;
    
    public class Test9 {
    
        /*public double test(Double x,int flage){
            double returnData = 0.0;
            double x1 = 0;
            double x2 = x;
            double point = ;
            while(new BigDecimal(x).)
    
    
            return returnData;
        }*/
    
        /*public int test(int[] arr){
            int maxtotal = 0;
            for(int i = 0;i<arr.length;i++){
                int sumTotal =arr[i];
                int sumTotalMax = 0;
                for(int j = i+1;j<arr.length;j++){
                    if(sumTotal+arr[j]>sumTotalMax){
                        sumTotalMax = sumTotal+arr[j];
                    }
                    sumTotal=sumTotal+arr[j];
                }
                if(sumTotalMax>maxtotal){
                    maxtotal = sumTotalMax;
                }
            }
            return maxtotal;
        }*/
    
    
        public int test(int[] arr){
            int maxtotal = 0;
            for(int i = 0;i<arr.length;i++){
                int sumTotal =arr[i];
                int sumTotalMax = 0;
                //这里做了一个判断判断的依据是前一个数是整数，后一个数是负数
                if(i+1<arr.length&&sumTotal+arr[i+1]<arr[i+1]){
                    continue;
                }
                for(int j = i+1;j<arr.length;j++){
                    if(sumTotal+arr[j]>sumTotalMax){
                        sumTotalMax = sumTotal+arr[j];
                    }
                    sumTotal=sumTotal+arr[j];
                }
                if(sumTotalMax>maxtotal){
                    maxtotal = sumTotalMax;
                }
            }
            return maxtotal;
        }
    
        public static void main(String[] args) {
    
            Test9 test9 = new Test9();
            int[] arr = {-2,11,-4,13,-5,2};
            System.out.println(test9.test(arr));
    
        }
    }