세 스택의 가능한 최대 합계 찾기

주어진 3 개의 배열 stack1 [], stack2 [] 및 stack3 [] 스택 그리고 이들의 시작 색인 배열 정상으로 취급됩니다. 세 스택 모두에서 가능한 공통 최대 합계를 찾으십시오. 즉, stack1, stack2 및 stack3의 요소 합계가 같습니다. 공통 최대 합을 찾기 위해 각 배열에서 상단을 제거 할 수 있습니다.

핀

예

입력 

스택 1 [] = {3, 2, 1, 1, 1}
stack2 [] = {4, 3, 2}
stack3 [] = {1, 1, 4, 1}

출력:   5

입력 

stack1 [] = {3, 10}
stack2 [] = {4, 5}
stack3 [] = {2, 1}

출력:   0

암호알고리즘

이제 우리는 세 스택의 최대 합계 가능한 등합 찾기의 문제 설명을 알고 있습니다. 따라서 이제 구현에 사용되는 알고리즘을 빠르게 읽으십시오.

1. 스택을 나타내는 3 개의 배열을 초기화합니다.
2. 세 배열의 요소 합계를 개별적으로 계산합니다. 또한 모든 배열의 맨 위, 즉 첫 번째 요소를 3으로 저장할 0 개의 변수를 선언합니다.
3. true 인 동안 배열의 상단이 크기와 같은지 확인하고 0을 반환합니다.
4. 그렇지 않으면 모든 배열의 개별 합계가 같으면 합계를 반환합니다.
5. 첫 번째 배열의 합이 두 번째 배열과 세 번째 배열의 개별 합보다 크거나 같으면 첫 번째 배열의 상단 요소를 합에서 빼고 첫 번째 배열의 상단 변수를 증가시킵니다.
6. 그렇지 않으면 두 번째 배열의 합이 첫 번째 배열과 세 번째 배열의 개별 합보다 크거나 같으면 두 번째 배열의 최상위 요소를 합에서 빼고 두 번째 배열의 최상위 변수를 증가시킵니다.
7. 그렇지 않으면 세 번째 배열의 합이 첫 번째 배열과 두 번째 배열의 개별 합보다 크거나 같으면 해당 합계에서 세 번째 배열의 최상위 요소를 빼고 세 번째 배열의 최상위 변수를 증가시킵니다.

세 스택의 가능한 최대 합계를 찾는 C ++ 프로그램

#include<bits/stdc++.h> 
using namespace std; 

int maxSum(int stack1[], int stack2[], int stack3[], int n1, int n2, int n3){ 
    int sum1 = 0, sum2 = 0, sum3 = 0; 
    
    for(int i=0; i < n1; i++){ 
        sum1 += stack1[i]; 
    }      

    for(int i=0; i < n2; i++){ 
        sum2 += stack2[i]; 
    } 
    
    for(int i=0; i < n3; i++){ 
        sum3 += stack3[i]; 
    }
    
    int top1 =0, top2 = 0, top3 = 0;
    
    while(1){ 
        if((top1 == n1) || (top2 == n2) || (top3 == n3)){ 
            return 0; 
        }
        
        if((sum1 == sum2) && (sum2 == sum3)){ 
            return sum1; 
        }
        
        if((sum1 >= sum2) && (sum1 >= sum3)){ 
            sum1 -= stack1[top1++]; 
        }
        
        else if((sum2 >= sum3) && (sum2 >= sum3)){ 
            sum2 -= stack2[top2++]; 
        }
        
        else if(sum3 >= sum2 && sum3 >= sum1){ 
            sum3 -= stack3[top3++]; 
        }
    } 
} 
int main(){

    int stack1[] = {3, 2, 1, 1, 1}; 
    int stack2[] = {4, 3, 2}; 
    int stack3[] = {1, 1, 4, 1}; 
    
    int n1 = sizeof(stack1)/sizeof(stack1[0]); 
    int n2 = sizeof(stack2)/sizeof(stack2[0]); 
    int n3 = sizeof(stack3)/sizeof(stack3[0]); 
    
    cout << maxSum(stack1, stack2, stack3, n1, n2, n3) << endl; 
    
    return 0; 
}

5

세 스택의 가능한 최대 합계를 찾는 Java 프로그램

class MaxPossibleSum{ 

    public static int maxSum(int stack1[], int stack2[], int stack3[], int n1, int n2, int n3){ 
        int sum1 = 0, sum2 = 0, sum3 = 0; 
        
        for(int i=0; i < n1; i++){ 
            sum1 += stack1[i]; 
        } 
        
        for(int i=0; i < n2; i++){ 
            sum2 += stack2[i]; 
        }
        
        for(int i=0; i < n3; i++){ 
            sum3 += stack3[i]; 
        }
        
        int top1 =0, top2 = 0, top3 = 0; 
        int ans = 0; 
        
        while (true){ 
        
            if((top1 == n1) || (top2 == n2) || (top3 == n3)){ 
                return 0; 
            }
            
            if((sum1 == sum2) && (sum2 == sum3)){ 
                return sum1; 
            }
            
            if((sum1 >= sum2) && (sum1 >= sum3)){ 
                sum1 -= stack1[top1++]; 
            }
            
            else if((sum2 >= sum3) && (sum2 >= sum3)){ 
                sum2 -= stack2[top2++]; 
            }
            
            else if((sum3 >= sum2) && (sum3 >= sum1)){ 
                sum3 -= stack3[top3++]; 
            }
        } 
    } 
    
    public static void main(String[] args){
        int stack1[] = {3, 2, 1, 1, 1}; 
        int stack2[] = {4, 3, 2}; 
        int stack3[] = {1, 1, 4, 1}; 
        
        int n1 = stack1.length; 
        int n2 = stack2.length; 
        int n3 = stack3.length; 
        
        System.out.println(maxSum(stack1, stack2, stack3, n1, n2, n3)); 
    } 
}

5

복잡성 분석

시간 복잡성 : O (n1 + n2 + n3) 여기서 n1, n2 및 n3은 각각 stack1, stack2 및 stack3 배열의 요소 수입니다.

보조 공간 : O (1) 상수 공간을 사용하고 있습니다.

참조