जावा

Question

में कडेन एल्गोरिदम मेरे पास जावा में कडेन के एल्गोरिदम का निम्नलिखित कार्यान्वयन है। यह मूल रूप से संगत subarray के अधिकतम योग को खोजने के लिए है।

String[] numbers = string.split(","); 
       int max_so_far = 0; 
       int max_ending_here = 0; 
       for (int i = 0; i < numbers.length-1;i++){ 
        max_ending_here = max_ending_here + Integer.parseInt(numbers[i]); 
        if (max_ending_here < 0) 
         max_ending_here = 0; 
        if (max_so_far < max_ending_here) 
          max_so_far = max_ending_here; 
       } 
       System.out.println(max_so_far); 

हालांकि इस अगर वहाँ एक सरणी में एक नकारात्मक और सकारात्मक संख्या का एक संयोजन है काम नहीं करता है, उदाहरण के लिए निम्नलिखित:

2,3,-2,-1,10 

जो एक 12 लौटाना चाहिए अधिकतम के रूप में। अभी तक यह 5

Answer 1

आप एल्गोरिदम कार्यान्वयन ठीक दिखता है, लेकिन आपके लूप सशर्त i < numbers.length-1 नहीं करता है: यह सरणी के अंत में केवल 1 छोटा बंद करता है। i < numbers.length :-)

Answer 2

यह क्या करना चाहिए यह मेरे लिए काम करता है:

String string = "2,3,-2,-1,10"; 
    String[] numbers = string.split(","); 
    int max_so_far = 0; 
    int max_ending_here = 0; 
    for (String num : numbers) { 
     int x = Integer.parseInt(num); 
     max_ending_here = Math.max(0, max_ending_here + x); 
     max_so_far = Math.max(max_so_far, max_ending_here); 
    } 
    System.out.println(max_so_far); 

Answer 3

मीकल Šrajer से ऊपर जवाब के बारे में:

लाइन # 7: max_ending_here = Math.max (0, max_ending_here + x);

होना चाहिए:

max_ending_here = Math.max (एक्स, max_ending_here + x);

... परिभाषित here

Answer 4

बहुत देर हो गई के रूप में Kadane एल्गोरिथ्म के अनुसार, लेकिन किसी को भविष्य में यह आवश्यक है या नहीं।

public static void kadaneAlgo(int[][] array) 
    for(int i = 1; i < array.length; i++){ 
      int max_value_index_i = numberOrSum(array[i], past); 
      if(max_value_index_i > sum){ 
       sum = max_value_index_i; 
      } 
      past = max_value_index_i; 

     } 
     System.out.println("Max sum from a contiguous sub array is : " + sum); 
    } 

    public static int numberOrSum(int number, int past){ 
     return Math.max(number, number+past); 
    }