程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 在一個數組中找到連續的子數組最大的乘積

在一個數組中找到連續的子數組最大的乘積

編輯:C++入門知識

在一個數組中找到連續的子數組最大的乘積


 

 

例如輸入[2,3,-2,4]?

符合條件的子數組應該是[2,3],他們的乘積是6

 

/**
 * @Author jiangfq
 * 
 */
package com.test;

/**
 * @author jiangfq
 *
 */
public class Solution {

	/**
	 * @Author jiangfq
	 *
	 */
	public static void main(String[] args) {
		int[] a = {-3,0,1,-2};
		Solution s = new Solution();
		int b = s.maxProduct(a);
		System.out.println(b= + b);
	}
	
	public int maxProduct(int[] A) {
        if(A.length == 0) {  //如果是0,則返回0
        	return 0;
        } else if(A.length == 1) {  //如果有一個
        	return A[0];
        } else if(A.length == 2) {  //如果數組有兩個元素
        	if(A[0] > A[0]*A[1]) {
        		return A[0];
        	} else if(A[1] > A[0]*A[1]) {
        		return A[1];
        	}
        	return A[0]*A[1];
        } else {
        	int ood = 0; //記錄負數的個數
        	int sum = 1;
        	for(int i = 0; i < A.length; i++) {  //先計算負數個數以及總乘積
        		sum *= A[i];
        		if(A[i] < 0) {
        			ood++;
        		} 
        	}
        	if(ood !=0 && ood%2==0 && sum != 0) {
        		return sum;
        	} else {
        		int max = A[0];   //記錄當前的最大值
        		int prev = max;  //記錄前一個最大值,方便與當前最大值做比較
        		for(int i = 0; i < A.length; i++) {
        			max = A[i];
        			int s = max;
        			if(s == 0) {  //如果是0,則跳過
        				continue;
        			}
        			for(int j = i+1; j < A.length; j++) {
        				s *= A[j];
        				if(max < s) {
        					max = s;
        				}
        			}
        			if(prev < max) {
        				prev = max;
        			}
        		}
        		return prev;
        	}
        }
    }

}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved