एल्गोरिथ्म एक सरणी में सबसे बड़ा ड्रॉप

Question

मैं एक एल्गोरिथ्म सवाल है खोजने के लिए अधिकतम {सरणी [i] -एरे [जे]} एक बाधा के साथ: i> जे।

सरल समाधान यह है कि दो लूप और I और j के सभी संभावित मानों के माध्यम से जाते हैं, लेकिन समय जटिलता ओ (एन * एन) है।

और एक बेहतर समाधान मुझे लगता है कि पहले सरणी के इंडेक्स को मैप करना है, सरणी को सॉर्ट करें और सबसे बड़ी बूंद खोजने के लिए सरणी के माध्यम से जाएं। यह जटिलता ओ (nlogn) है।

रैखिक समय जटिलता के साथ कोई समाधान है? और कैसे?

पीएस: मैंने एक बार एक रैखिक समाधान सोचा: दो अतिरिक्त सरणी बनाएं, एक को दिए गए सरणी के अधिकतम मूल्य को शुरुआत से अंत तक रिकॉर्ड करना है, और दूसरे को अंत से लेकर शुरुआत तक न्यूनतम मूल्य तक रिकॉर्ड करना है। फिर, दो सरणी एक पास के माध्यम से जाओ। हालांकि, किसी ने सोचा कि सही ढंग से नहीं और बहुत बड़ी जगह लेना। तो मैं एक बेहतर समाधान जानना चाहता हूं। - lijuanliu

Answer 1

बनाएं नया 2 सरणियों:

max[i] = max { arr[0], arr[1], ..., arr[i] } 
min[i] = min { arr[n-1], arr[n-2], ..., arr[i] } 
(max is the maximum from first to i, min is the minimum from i to last) 

अब, auxilary सरणियों पुनरावृति और पाते हैं अधिकतम अंतर max[i] - min[i]

इसके लिए कुल 3 पुनरावृत्तियों की आवश्यकता होती है और इस प्रकार O(n) है।

शुद्धता का प्रमाण (दिशा-निर्देश):

1. फिर, max[i] >= arr[j] (हम पहले से ही इसे पारित क्योंकि), और:

   सबसे बड़ी ड्रॉप सूचकांक i से सूचकांक j, जहां i<j को होने दो min[i] <= arr[i] - इस प्रकार max[j] - min[j] >= arr[i] - arr[j], और एल्गोरिदम द्वारा प्रदान किया गया उत्तर कम से कम इष्टतम के रूप में अच्छा है।

2. इसके अतिरिक्त, क्योंकि सबसे बड़ी बूंद i,j है, वहाँ नहीं किसी भी k<j ऐसी है कि arr[k] < arr[i] हो सकता है, क्योंकि तब सबसे बड़ी बूंद arr[j] करने के लिए arr[k] से हो जाएगा।Similary - वहाँ k>j ऐसी है कि arr[k] < arr[j], एक ही कारण के लिए नहीं किया जा सकता है - और इस max[j]-min[j] <= arr[i] - arr[j]

ऊपर से हम उस max[j]-min[j] = arr[i] - arr[j] निष्कर्ष निकाल सकते हैं। सभी एक औपचारिक पूरा सबूत के लिए छोड़ दिया जाता है पता चलता है कि प्रत्येक k आप max[k]-min[k] <= max[j] - min[j] पाने के लिए है, और यह वास्तव में मामला है, अन्यथा वहाँ कुछ u<k हैं, v>k ऐसी है कि max[k]=arr[u], min[k]=arr[v], और आप प्राप्त है कि arr[u] - arr[v] > arr[i] - arr[j] है, जो तथ्य यह है कि i,j है के विपरीत है सबसे बड़ी बूंद

QED

Answer 2

मैं केवल ओ (nlogn) के बारे में सोच सकता हूं, लेकिन यह एक ही जटिलता को तेज करना चाहिए और सबसे बड़ी बूंद को ढूंढना और खोजना चाहिए।

आप क्या कर सकते हे (एन) में लगातार संख्या के अंतर की गणना करने के लिए और उसके बाद समस्या निरंतर उप सरणी जो हे होगा (nlogn)

Answer 3

के मैक्स (योग) पाने के लिए कम हो जाएगी है

आपको दो चीजों का ट्रैक रखने की आवश्यकता है:

अधिकतम संख्या जो आप तत्व के लिए प्रतीत होती है, और सबसे बड़ी संख्या जो आप सबसे बड़ी संख्या के संबंध में प्रतीत होती है (यानि पहले अधिकतम संख्या, तत्व को घटाएं I)। यह समय में ओ (एन) और अंतरिक्ष में ओ (1) होगा।

यह समस्या बिल्कुल "शेयर खरीदने/बेचने" साक्षात्कार सवाल, समाधान यहां पाया जा सकता है: Maximum single-sell profit

Answer 4

public static int maxDrop(int[]array){ 

    int maxDrop =0,drop=0,min=array[0]; 

    for(int i=1;i<array.length;i++){ 

     if(array[i]<min){ 
      min=array[i]; 
     } 

     drop = array[i]-min; 

     if(drop>maxDrop){ 
      maxDrop=drop; 
     } 

    } 

    System.out.println(maxDrop); 
    return maxDrop; 

} 

Answer 5

हे (एन) के लिए अतिरिक्त जगह के बिना समाधान:

public int maxDrop(int[] a) { 
    int max = a[0]; 
    int maxDrop = -1; 
    for (int i = 0; i < a.length; i++) { 
     if (max < a[i]) { 
      max = a[i]; 
     } 
     else { 
      int drop = max - a[i]; 
      maxDrop = Math.max(maxDrop, drop); 
     } 
    } 
    return maxDrop; 
}