졸렬한 알고리즘: 하위 배열 의 최대 합 을 구하 십시오.

제목: 성형 배열 을 입력 하 십시오. 배열 에는 양수 도 있 고 마이너스 도 있 습 니 다.배열 에서 연속 되 는 하나 또는 여러 개의 정수 가 하나의 키 배열 을 구성 하고 모든 하위 배열 은 하나의 합 이 있다.모든 하위 배열 의 합 의 최대 치 를 구하 십시오.시간 복잡 도 를 O (n) 로 요구 합 니 다.예 를 들 어 입력 한 배열 은 1, - 2, 3, 10, - 4, 7, 2, - 5 이 고 가장 큰 하위 배열 은 3, 10, - 4, 7, 2 이기 때문에 이 하위 배열 의 것 과 18 로 출력 된다.O (N) 의 복잡 도 이기 때문에 사용 해 야 할 DP 의 사상 은 현재 요소 의 합 (가장 좋 은 상태, 가장 큰 상태) 을 기록 하고 이 를 현재 얻 은 것 과 비교 하 며 크 면 업데이트 하고 그렇지 않 으 면 계속 해 야 한다.상태의 누적 은 이 과정 을 따른다. 현재 와 0 보다 적 으 면 이 상 태 를 포기 하고 0 으로 돌린다.
나의 졸렬한 생각: 1. 마 이 너 스 를 만 나 는 것 은 현재 와 값 sum 을 부분 변수 result 로 저장 하 는 것 입 니 다.2. 음 수 를 더 하면 sum 값 이 0 보다 작 습 니 다.다음 것 부터 다시 계산 합 니 다.첫 번 째 정 수 를 찾 아 다시 화 해 를 구하 기 시작 하 다.첫 번 째 졸렬한 코드 는 참고 없 이 자신 이 썼 다.

        int[] arr={4,0,-3,10,-4,7,-2,5};
        int sum=0;
        int result=-100;        //       
        for(int i=0;i0){                    //    0，sum   
                sum=sum+arr[i];
            }else {                         //    0
                if(sum>result){              //  result
                    result=sum;
                }
                if(sum+arr[i]>0){            //           0
                   sum=sum+arr[i];        //   0，     
                }else {                          //  0， sum   0
                   sum=0;
                }
            }
        }
        
        if(sum>result){                      //      sum  result
            result=sum;
        }
        
        System.out.println("result="+result+" sum="+sum );

위의 알고리즘 은 sum + arr [i] < 0 의 상황 sum = 0 을 최적화 시 킬 수 있 습 니 다. 여 기 는 다음 정 수 를 찾 는 것 으로 바 꿔 야 합 니 다.이렇게 모든 음 수 는 두 번 의 대 비 를 하지 않 고 한 번 에 0 보다 작은 대 비 를 하면 된다.

        int[] arr={1, -2, 3, 10, -4, 7, 2, -5};
        int sum=0;
        int result=arr[0];
        for(int i=1;i=0){
                sum=sum+arr[i];
            }else {
                if(sum>result){
                    result=sum;
                }
                
                if(sum+arr[i] < 0){
                   while(iresult){
            result=sum;
        }
        System.out.println("result="+result);

위의 프로그램 은 모두 음 수 를 입력 할 때 달 릴 수 없다.다음 프로그램 은 가능 합 니 다.

        int[] arr={-9, -2, -3, 10, 5, -1,-2, 5};
        int sum=arr[0];
        int result=arr[0];
        for(int i=1;i=0){
                if(sum<0){
                    sum=arr[i];   // sum     
                }else {
                    sum=sum+arr[i];
                }
            }else {
                if(sum>result){
                    result=sum;
                }
                
                if(sum+arr[i] < 0){
                   sum=arr[i];             //     ，       
                }else {
                   sum=sum+arr[i];
                }
                   
            }
               
        }
        if(sum>result){
            result=sum;
        }
        System.out.println("result="+result);

모두 마이너스 일 때 sum 값 은 하나의 마이너스 입 니 다.result 와 비교 하면 result 를 업데이트 할 수 있 습 니 다.
관건 적 인 사상 은 마 이 너 스 를 만 났 을 때 이 마이너스 부터 계산 하 는 것 이다.그러나 다음 수가 정수 인 것 을 만 났 을 때 sum 을 이 정수 로 초기 화 합 니 다.
위의 코드 는 순 전 히 자기가 쓴 것 이 니, 정 답 은 역시 인터넷 을 보 세 요!!
http://www.cnblogs.com/aLittleBitCool/archive/2011/01/16/1936842.html 인터넷 에서 의 표준 답안 은 여전히 훨씬 간단 하 다 는 것 을 발견 하 였 다.속되다
직접 추가 하면 서 최대 치 를 업데이트 합 니 다.0 보다 작 으 면 바로 다시 추가!!!간단 해 죽 겠 어 요.